cracking-the-coding-interview第16章中等难度11题攻略：单词频率统计、线段相交等刁钻题型的破解技巧

cracking-the-coding-interview第16章中等难度11题攻略单词频率统计、线段相交等刁钻题型的破解技巧【免费下载链接】cracking-the-coding-interview:books: C and Python solutions with automated tests for Cracking the Coding Interview 6th Edition.项目地址: https://gitcode.com/gh_mirrors/cra/cracking-the-coding-interview正在准备算法面试的同学可以把 cracking-the-coding-interview 这个项目当作一份带自动测试的解题手册它对《Cracking the Coding Interview》CTCI第6版的题目提供了 C 与 Python 双语言实现并用单元测试逐题验证。本章攻略聚焦书中第16章中等难度最刁钻的11道编程题——单词频率统计、线段相交判定、最大子数组和等逐题拆解破解技巧帮你把会做变成讲得清。第16章11题速查总览题型、核心思路与复杂度先花30秒扫一遍全章地图心里有数再动手编号题型核心思路时间复杂度16.01不使用临时变量交换两个数加减法三步 / 异或O(1)16.02书中任意单词频率统计哈希表预计算 O(1) 查询O(1)/次16.03判断两条线段是否相交无限直线求交点 线段范围校验O(1)16.04判断井字棋是否获胜递归枚举全部局面存入哈希表O(1)/次16.05计算 N! 末尾0的个数统计因子5的个数O(logN)16.06两数组中差值最小的数对排序 归并式双指针O(MlogMNlogN)16.07不用 if 和比较符求两数最大值整数除法的 0/1 特性 位运算O(1)16.10存活人数最多的一年差分数组 前缀和O(N)16.11恰好 k 块木板的所有跳板长度枚举 K1 种组合 集合去重O(K)16.17最大连续子数组和Kadane 算法一次遍历O(N)16.19计算所有池塘的面积8 方向 DFS 原地标记O(N²)快速上手一条命令跑通11道题的全部单元测试本项目的最佳学习方式是测试先行先读懂tests.cpp里的用例再让make test变绿。git clone https://gitcode.com/gh_mirrors/cra/cracking-the-coding-interview.git cd cracking-the-coding-interview # Ubuntu: make configure-ubuntu / Mac: make configure-mac make test第16章的全部测试断言都写在根目录的tests.cpp中如factorialZeros(25) 6、wordFrequencies(the) 12等跑通make test即代表11题全部达标。构建配置见根目录的CMakeLists.txt与Makefile。单词频率统计哈希表预计算让每次查询都是 O(1) 16.02 要求设计方法查询书中任意单词的出现次数且题目追问了一句狠话如果这个算法要被运行很多次呢答案是把重复计算换成一次预计算第一遍扫书统计每个单词的计数存入哈希表unordered_map之后任意查询直接查表O(1) 返回。这是面试中的高频套路——凡是同数据、多次查询的场景第一反应都该是预计算 哈希表。C 实现见 problem_16_02_wordFrequencies.h其中makeDatabase()建库、wordFrequencies()查询职责划分非常清晰。线段相交判定算法先求无限直线交点再做范围校验16.03 是最容易在边界上翻车的一道几何题平行、共线、端点恰好相接……各种情况都想不全。本项目的策略把问题拆成两步非常干净斜率不等把两条线段无限延伸直接代数求交点x (b2-b1)/(m1-m2)然后用inBounds()校验交点是否同时落在两条线段范围内斜率相等只有端点重合才算相交直接比较端点坐标。一个容易忽视的细节实现用approxEqual()做浮点比较避免直接判等踩坑。头文件里构造LineSegment2时还会把两点按 x 坐标排序让后续判断更简单——见 problem_16_03_intersection.h。最大子数组和Kadane 算法一次遍历拿答案16.17 就是大名鼎鼎的最大子数组和问题。核心洞察一句话就能讲清只要某段子数组的前缀和变成负数这段前缀就必然拖后腿直接把累计和重置为 0。于是只需一个指针、两个变量当前和、最大值一遍扫描O(N) 时间、O(1) 空间收尾。实现见cpp_solutions/chapter_16_moderate/problem_16_17_contiguousSequence.h注释里还特别交代了两个极端全正数时结果是整个数组之和全负数时结果是最大单个元素——面试时能主动说出这两种边界基本就稳了。存活人数最多的一年披着人口统计外衣的前缀和16.10 暴力做法是对每个人都遍历其存活年份代价 O(N×年份跨度)。本项目用了更漂亮的差分 前缀和开一个年份范围的数组每个人出生年1、死亡年的下一年-1从左到右扫描并累计和累计和第一次到达峰值的位置就是答案。总代价 O(N) 时间、O(1) 空间见problem_16_10_livingPeople.h的算法注释。这套区间转差分数组的手法对会议室预约、座位分配、流量统计题同样通用强烈推荐记进面试笔记。剩余7道题速破一题一句话讲透16.01 交换两数a a b; b a - b; a a - b三步走或全程异或见problem_16_01_swapNumbers.h。16.05 阶乘末尾0末尾的0来自因子10 2×5而5总是更稀缺只需反复n / 5累加商即可factorialZeros(25) 6。16.06 最小差值对两数组分别排序后像归并排序的 merge 步骤那样并一遍候选对只可能是归并时相邻的一对对答案在 O(MN) 内诞生。16.04 井字棋判定9 格每格 3 种状态共 3⁹ 19683 种局面。用递归树枚举全部局面、胜负结果存入哈希表之后每次查询 O(1)——典型的用空间换时间。16.07 无比较符求最大值小数除以大数恒为 0把商转成 0/1 当伪布尔再借位运算选出大者彻底绕开 if。16.11 跳板长度k 块木板中设短板 i 块0 ≤ i ≤ K长度只有 K1 种可能用unordered_set去重注意 k0、短长板等长这两个陷阱。16.19 池塘面积遍历矩阵遇到 0水就发起 8 方向 DFS含对角线沿途原地改值标记已访问DFS 返回的计数即一个池塘的面积全部收进 multiset。第16章解题思维模式总结把11题收敛成5个套路通读本章11题其实只考5种思维模式预计算 哈希表16.02 单词频率、16.04 井字棋——同数据多次查询的标配差分/前缀和16.10 存活人数——区间问题数组化的利器排序 归并16.06 最小差值——把 O(M×N) 降到 O(MN)贪心一次遍历16.17 Kadane——状态只保留当前最优DFS/递归 原地标记16.19 池塘——图连通问题的基本盘。面试前把cpp_solutions/chapter_16_moderate/下每个头文件的算法注释读一遍每题都写了 TEST CASES、ALGORITHM、TIME/SPACE 三段式说明再对照tests.cpp的用例自测口述中等题就能从做对升级到讲透 ✅。相关源码与测试文件位置C 第16章全部11题cpp_solutions/chapter_16_moderate/含problem_16_02_wordFrequencies.h、problem_16_03_intersection.h、problem_16_17_contiguousSequence.h等头尾配对文件Python 版第16章python_solutions/chapter_16_moderate/含problem_16_01_swap_numbers.py、problem_16_03_intersection.py单元测试根目录tests.cppC/Catch2与tests.pyPython构建与测试入口根目录Makefile、CMakeLists.txt【免费下载链接】cracking-the-coding-interview:books: C and Python solutions with automated tests for Cracking the Coding Interview 6th Edition.项目地址: https://gitcode.com/gh_mirrors/cra/cracking-the-coding-interview创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考