★ FEATURED ARTICLE 我不是那种一上来就列一堆题号的人但今天是《算法题打卡》的第 9 天我确实想先聊两句“选题逻辑”。坚持到第九天最大的变化不是手速快了而是看到热搜词里“暴力枚举算法”“剪枝算法”“kmp算法”“贪心算法”这些词的时候已经能下意识把它映射到具体题型上枚举配剪枝、贪心配二分、字符串配前缀函数。这一天我特意挑了四道题对应几个高频考点组合总和、在 D 天内送达包裹、KMP 手写匹配、二叉树层序遍历。它们都不是偏题怪题但每一道都能把“会背模板”和“真懂原理”的人区分开。如果你正在刷题初期这篇就当一份带思路的打卡记录看如果你已经刷了一阵子里面有几处边界处理和复杂度判断的经验是我踩过坑之后才学到的。1. 第9天选题思路从热搜词里筛出四道题1.1 四道题到底对应哪些算法热词我每次打卡前会先看一眼当天的热词列表不是为了追热点而是看大家对哪类问题讨论得最多。这一天的高频词里算法相关的基本都集中在枚举、剪枝、贪心、字符串匹配、排序、数据结构这些基础方向上。我从中挑了四道题一一对应题目考点对应热词为什么选它LeetCode 39 组合总和回溯 剪枝暴力枚举算法、剪枝算法回溯模板人人会背剪枝细节决定能不能过LeetCode 1011 在 D 天内送达包裹的能力二分答案 贪心模拟枚举算法、贪心算法非典型二分的代表check 函数是灵魂LeetCode 28 实现 strStrKMP 字符串匹配kmp 算法面试高频背模板容易讲原理难LeetCode 102 二叉树的层序遍历BFS 分层数据结构与算法队列快照 size 的技巧很实用选择的标准很简单这四道题不是我随机翻的而是针对我最近一周暴露出的薄弱点刻意安排的。回溯我经常写完就跑不过大样例二分我只会写有序数组查找字符串匹配停留在理论树的层序遍历以前我习惯用 null 分隔符思路不够通用。一天集中打这四个补丁效率比漫无目的地刷二十道要高得多。1.2 我给自己定的选题标准刷题打卡这事最难的不是做题是坚持。而坚持的前提是“每天的任务可完成”。我给自己定过三条选题规则现在已经变成固定动作每类题先做最经典的模板题再做变种不直接挑战高难度综合题。当天选的题必须能在 30 分钟内写出完整代码超过 30 分钟就看题解不硬耗。每道题必须记录一处“之前会忽略的细节”哪怕只是一句话也要写进当天的笔记。这三条规则帮我避免了两个常见陷阱一是好高骛远打开困难题死磕一晚上第二天就放弃二是刷数量不刷质量一天过十道简单题回头全忘了。第九天回头看真正有用的恰恰是那些被记录下来的细节比如回溯里传 i 还是传 i1二分里取中位数是左偏还是右偏KMP 失配时到底回退到哪。2. 第一题 组合总和回溯模板好写剪枝技巧才决定成败2.1 题目与一个容易被忽略的前提LeetCode 39 的原题是这样的给一个无重复元素的整数数组 candidates 和一个目标数 target找出所有可以使数字和为 target 的组合candidates 里的数字可以无限制重复被选取。这题第一眼确实像暴力枚举把所有可能的组合都试一遍等于 target 就记录下来。但直接枚举会遇到两个问题一是组合的“顺序不同算同一种”如果不加控制会出现 [2,3] 和 [3,2] 都进答案二是组合数量可能爆炸如果数组里有 1那 target 多大就要递归多少层。第一个问题靠 dfs 的 startIndex 参数解决第二个问题靠排序剪枝解决但前提是——先把数组排序。我见过有人不排序也把题 AC 了靠的是在结果里去重或者提前判断剩余 target 是否小于当前数来返回但那样代码会绕而且容易漏。2.2 C 代码实现与边界细节class Solution { public: void dfs(vectorint candidates, int target, int start, vectorint path, vectorvectorint ans) { if (target 0) { ans.push_back(path); return; } for (int i start; i candidates.size(); i) { if (candidates[i] target) break; // 排序后的核心剪枝 path.push_back(candidates[i]); dfs(candidates, target - candidates[i], i, path, ans); path.pop_back(); } } vectorvectorint combinationSum(vectorint candidates, int target) { sort(candidates.begin(), candidates.end()); vectorvectorint ans; vectorint path; dfs(candidates, target, 0, path, ans); return ans; } };几个细节dfs里传的是i而不是i1因为题目允许同一个数字重复选取。如果题目改成每个数字只能用一次那就传i1比如 LeetCode 40。if (candidates[i] target) break;这行只有在数组有序的情况下才成立。因为后面所有的数都更大当前数如果已经大于剩余 target后面不可能再有可行解直接终止循环即可。剪枝发生在这里但这不是唯一的剪枝方向。如果数字可以重复另一个常见剪枝是提前记录前缀和判断剩余位置上即使全选最小数也无法凑齐 target就直接回溯。对于数据范围更大、更接近现实的题目这个剪枝会更有效。2.3 枚举、剪枝、去重三件事的边界感这道题给我的最大启发是很多人把“暴力枚举”和“剪枝优化”当成两个对立面其实它们是同一个过程。暴力枚举是先定好搜索空间剪枝是把搜索空间中明显没希望的分支砍掉。写的时候先保证枚举部分是正确的再考虑优化这个顺序一定不要反。否则一旦剪枝写错连正确性都保不住。另一个值得讲的是去重。这道题因为数组无重复元素所以不存在“同一层选了相同的数字导致重复组合”的问题。但 LeetCode 40 里有重复元素就需要在 for 循环里加一行if (i start candidates[i] candidates[i - 1]) continue;意思是同一层递归中如果当前数字和上一个数字相同直接跳过。这个去重逻辑配合排序非常经典能延伸出一整类“组合去重”的题。面试时面试官很喜欢在这道题后面跟一句“如果数组里有重复元素怎么办”本质上就是在考这个。3. 第二题 在 D 天内送达包裹二分答案为什么比直接模拟更好写3.1 先理解 check 函数再谈二分LeetCode 1011 是这样的传送带上的包裹 weights 必须按顺序运走不能打乱顺序要求在第 days 天内运完求满足条件的最小运载能力。我见过不少人第一反应是直接模拟一天一天地装尝试让运载能力符合要求。但运载能力的取值区间很大直接枚举太慢。正确的做法是二分答案把“求最小可行值”转换成“判断某个值是否可行”。关键在 check 函数的写法bool check(vectorint weights, int days, int cap) { int need 1, cur 0; for (int w : weights) { if (w cap) return false; // 单个货物都放不下直接不可行 if (cur w cap) { need; cur w; } else { cur w; } } return need days; }这里有一个我踩过的坑如果单个包裹重量大于当前测试的运载能力应该直接返回 false而不是假装把它装进新的一天。早期我写 check 的时候没加这行判断结果当 days 恰好很大时容量比最大包裹小也会被判成可行导致二分结果错误。这个问题非常隐蔽因为输入数据一般不会让 days 大得太离谱但如果把边界值卡死就能测出来。3.2 左闭右开还是左开右闭防死循环的模板二分答案的写法有很多流派我自己常用的是“左开右闭 l 1 r”的模板不容易死循环int shipWithinDays(vectorint weights, int days) { int maxW 0, sumW 0; for (int w : weights) { maxW max(maxW, w); sumW w; } int l maxW - 1; // 严格小于最小可行值 int r sumW 1; // 严格大于最大可行值 while (l 1 r) { int mid l (r - l) / 2; if (check(weights, days, mid)) r mid; else l mid; } return r; }边界的设计逻辑是这样的运载能力至少要能装下最重的单个包裹所以最小可行值一定 ≥ maxW。运载能力取 sumW 时一天就能全部运完所以它一定可行。我把左边界取成 maxW - 1保证左边界严格不可行右边界取成 sumW 1保证右边界严格可行。while 循环用l 1 r而不是l r这样 mid 永远不会等于 l也就不会出现l mid导致的死循环。最后 r 停在最小可行值直接返回。这种写法比常见的while (l r)版本更容易讲清楚也更适合面试时手撕。当然如果习惯了l r r mid / l mid 1的模板也没问题关键是明白每个边界值的含义而不是死记。3.3 复杂度计算与面试中的加分表达二分答案的复杂度分两部分每次 check 需要遍历整个数组O(n)二分次数是 O(log(sumW))其中 sumW 是所有包裹重量之和。总复杂度 O(n log(sumW))在 n 是 10^4 级别的题里完全够用。面试时如果你能主动说清这个复杂度会让面试官觉得你有全局观。我习惯在写代码前先讲一句“这个问题的答案是单调的运载能力越大越容易完成任务所以可以用二分答案。check 函数每次 O(n)总共 O(n log sumW)。”这样一开口思路就已经清晰了。这道题的变种很多LeetCode 875 爱吃香蕉的珂珂、LeetCode 410 分割数组的最大值核心都是“最大值最小化”或者“最小值最大化”这种单调性极强的问题。刷完 1011 以后我建议把 875 和 410 连着做一遍会把这类题目彻底打通。4. 第三题 手撕 KMP与其背模板不如从失配推导 next4.1 从暴力匹配到快速失配跳转KMP 是那种“看起来懂一写就废”的算法。暴力匹配是主串指针往前走模式串每次失配都从头开始最坏复杂度 O(n * m)。KMP 的核心优化是把模式串的“已知匹配前缀”利用起来失配时不要从头开始而是跳到已经匹配上的最长前缀后面继续比。这个“已经匹配上的最长前缀”怎么求就是 next 数组。我用的定义是前缀函数next[i]表示模式串p[0..i]这个子串中最长相等前后缀的长度。4.2 C 代码next 数组构建与匹配主流程vectorint buildNext(const string p) { int n p.size(); vectorint next(n, 0); for (int i 1, j 0; i n; i) { while (j 0 p[i] ! p[j]) j next[j - 1]; if (p[i] p[j]) j; next[i] j; } return next; } int strStr(string haystack, string needle) { if (needle.empty()) return 0; vectorint next buildNext(needle); for (int i 0, j 0; i haystack.size(); i) { while (j 0 haystack[i] ! needle[j]) j next[j - 1]; if (haystack[i] needle[j]) j; if (j needle.size()) return i - j 1; } return -1; }构建 next 的过程很像动态规划i 从 1 开始扫描j 保存当前已经匹配上的前缀长度。如果当前位置的字符相等j 加一否则 j 不断回退到next[j-1]直到匹配或者 j 等于 0。这个“回退”和主串匹配中的失配跳转是同一个逻辑理解了它就理解了 KMP。匹配阶段更简单主串指针 i 从头到尾只扫一遍。当haystack[i]和needle[j]相等时j 加一失配时 j 回退。当 j 等于模式串长度时说明找到了完整匹配返回i - j 1。4.3 实测中容易踩的两个坑坑一网上的老模板喜欢把 next 数组整体右移next[0] -1失配时j next[j]。这个模板也能 AC但面试如果让你解释原理你会讲不清“为什么整体右移”“为什么 next[0] 是 -1”。我建议用前缀函数版本逻辑自洽从定义到代码都能对得上。坑二拿小样例手推 next 数组时很容易算错最长相等前后缀。我当时的解决办法是每次刷完 KMP固定拿一个例子完整推导一遍比如模式串ABABCABAB。它的 next 数组是[0,0,1,2,0,1,2,3,4]把“最长相等前后缀”这个定义落实到具体字符串上手推两步之后就再也忘不掉了。KMP 的代码量不大但细节多。如果哪次手写时卡住了我建议按这个顺序回忆第一next[i] 定义是啥第二构建时 i 从 1 开始j 跟随最长前缀第三失配时 j 回退到哪里第四主串匹配时 i 永远不回溯。记牢这四条KMP 基本不会写错。5. 第四题 二叉树的层序遍历BFS 快照 size 法的意外收获5.1 为什么不用 null 分隔符LeetCode 102 要求按层输出二叉树的节点值比如[ [3], [9,20], [15,7] ]。最直观的想法是 BFS 队列加 null 分隔符每遇到一个 null 就说明一层结束。但这个方法有个尴尬的地方如果某一层的最后一个节点恰好有右子树但左子树为空队列里就会出现多余的 null导致分层错误。用快照 size 法就完全不存在这个问题。vectorvectorint levelOrder(TreeNode* root) { vectorvectorint ans; if (!root) return ans; queueTreeNode* q; q.push(root); while (!q.empty()) { int sz q.size(); vectorint level; for (int i 0; i sz; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } ans.push_back(level); } return ans; }核心就一行进入循环时先取int sz q.size()这表示当前队列里恰好是上一层的节点数。然后 for 循环只处理这 sz 个节点过程中新加入的节点是下一层的不会干扰当前层。5.2 DFS 也能层序为什么面试优先选 BFS有人可能疑惑层序遍历是不是只能用 BFS其实 DFS 也可以递归时记录深度 depth把当前节点的值写进res[depth]即可。但面试里我建议优先用 BFS 快照 size 法原因是它天然符合“逐层扫描”的定义代码结构清晰而且很容易扩展到锯齿形层序遍历LeetCode 103 只要在偶数层把结果 reverse 一下就行。这道题还有一个隐形考点边界的处理。很多人在if (!root) return ans;这一步漏写导致队列入空后访问空指针。每道树的题我都会先确认 root 是否为空这也算是肌肉记忆了。5.3 层序遍历可以延伸出什么层序遍历不是孤立的知识点它可以用来做求二叉树最大宽度、判断完全二叉树、输出二叉树右视图等变种题。核心都是 BFS 分层区别只在于每层循环里处理的数据不同。刷完 102 后我顺手把 103 锯齿形层序、199 右视图都做了一遍基本是一套模板改几行的事。这种“一题带一题”的刷法比每次单打独斗效率高得多。6. 复杂度那点事什么时候写 O什么时候写 Θ6.1 热词这个问题到底在问什么热词里有一条“计算算法复杂度时什么时候用 o 什么时候用 θ”这是很多初学者的困惑。O 表示渐近上界Ω 表示渐近下界Θ 表示上下界同阶也就是精确阶。但工程和面试里大家几乎都写 O而且经常把它当成“最坏情况复杂度”来用。严格来说这是不严谨的。举几个例子遍历数组的次数是 n说复杂度是 O(n) 没问题但更精确的说法是 Θ(n)因为访问次数既是上界也是下界。二分查找的最坏情况执行 log n 次比较说 O(log n) 是描述上界没问题但如果明确知道最坏就是 log n用 Θ(log n) 更准确。快速排序平均情况比较次数大约是 n log n 量级工程上写成 O(n log n)这里的 O 实际上承担了 Θ 的角色因为大家默认讨论的是平均、最坏等多重情况叠加后的一个宽松结论。所以在算法题交流中“O”已经被泛化为“大概这个量级”你不会因为用了 O 而被批评。但如果是写论文或者做严谨的分析报告该用 Θ 的时候别写 O。判断标准很简单你给出的界是否紧如果紧想强调准确就用 Θ如果只是描述“不会超过这个量级”用 O。6.2 一个实用判断技巧看数据规模反推算法刷题时比纠结 O 和 Θ 更重要的是先通过数据范围判断预期复杂度。我列了个常用参考表数据规模可接受复杂度n ≤ 10O(n!) 或 O(2^n)n ≤ 20O(2^n) 或 O(n * 2^n)n ≤ 10^3O(n^2)n ≤ 10^5O(n log n)n ≤ 10^6O(n) 或 O(n log n) 且常数小拿到题目先看 n 的范围再倒推自己该写什么复杂度。比如 n 是 10^5你还写 O(n^2)大概率要超时这时候就要考虑排序后配合二分、或者双指针、或者哈希表。这种“先算复杂度再动手”的习惯能让你的代码在写之前就赢了一半。我在第 9 天打卡中反复用到了这个判断二分答案的 O(n log sumW)、KMP 的 O(n m)、层序遍历的 O(n)都属于能轻松通过中大规模数据的选择。7. 打卡第9天的节奏管理刷完题不等于吃透题7.1 三遍复盘法第 9 天最大的心得是做完题之后怎么复盘比怎么做题更重要。我现在的流程是标准三遍第一遍闭卷写。卡住 15 分钟就果断看题解不硬憋。看题解不是抄代码而是看别人的思路卡在哪里、用了什么我没见过的技巧。第二遍隔 2 小时再写一遍。这个间隔时间不长不短刚好能忘掉刚才的瞬时记忆。如果能独立写出来说明真的吸收了如果又卡住说明刚才只是“看懂”还没变成自己的。第三遍睡前用自然语言把思路讲一遍。比如这道题“组合总和是回溯加排序剪枝循环里传 i 是因为允许重复选取传 i1 就是不能用重复元素。”能把思路讲清楚才是真正吃透了。7.2 一个可持续的打卡模板我整理了一个适合每天用的打卡笔记模板你可以直接抄日期题目考点用时复杂度一句话心得第9天39回溯剪枝22minO(2^n) 最坏排序后 break 比 continue 果断得多第9天1011二分答案35minO(n log sumW)单个包裹大于容量要直接 return false第9天28KMP40minO(n m)前缀函数定义比整体右移模板更好讲第9天102BFS 分层12minO(n)先取快照 size再处理本层表格的价值在于它逼你每天输出一个“一句话心得”。哪怕是“今天这道题很简单”这种话写下来也会让你对当天的状态有感知。如果连续几天都只能写“没看懂”那就说明选题难度高了需要回调。7.3 最近热词给我下周的选题线索刷完这四道题后我翻了翻当天的热搜词发现“排序算法”相关的讨论特别多冒泡排序、归并排序、堆排序、快速排序、C STL 排序。这正好是我计划的下一块拼图。下周我准备开一个“排序算法全家桶”专题不只看复杂度而是把冒泡、选择、插入、快排、归并、堆排全部手写一遍再配合 STLsort的底层原理做对比分析。类似的主题在热词里还有“数据结构排序算法”和“c分治算法”感觉可以合并成一个大章节来写。如果你也刷到这里建议别只追新算法先把基础专题轮一遍收获会大得多。说实话打卡到第 9 天我并不觉得自己多了不起只是慢慢地养成了一个习惯拿到一道题先想数据范围能不能承受再想这道题考的是哪个专题最后才是动笔写代码。这个顺序如果从头就立住后面的刷题效率和心态都会好很多。下一步我准备把排序全家桶整理出来到时候接着聊。
阅读完成 · 觉得有帮助？
