第73天我在题单页面停了二十分钟一道都没点进去。桌面右下角的计时器还在跳昨天那道搜索旋转排序数组的最后一组边界用例又浮上来——不是不会是写完之后我自己都不确定它到底对不对。这个状态在刷题的前两个月从没出现过前面每一天都是新题、新知识点、新成就感到了第73天题目开始长得越来越像错误却开始藏得越来越深。这篇记录想聊的不是第73天我刷了哪几道题而是刷到这个阶段之后练习方式本身该怎么调。如果你刚起步这里面的模板和口诀可以直接抄如果你也卡在六七十天这个区间觉得题目都见过但正确率上不去那大概能省你几周的摸索。算法刷题这件事前30天拼的是能不能看懂题解30到70天拼的是能不能独立写出来70天往后拼的东西完全换了——是稳定性、是分类能力、是对我这个写法为什么对的确定感。下面按我这几天的实际复盘顺序展开从二分开始到字符串、图论、贪心剪枝最后说说节奏怎么改。1. 第73天我停了两个小时只为把题单重新排一遍1.1 中段疲劳期的真实症状标题叫刷题记录但真正值得记下来的从来不是今天AC了3题这种流水账。第73天我做了一件看起来很像偷懒的事把过去72天做过的187道题重新过了一遍标签结果发现自己有41道题在二分答案这一类上而滑动窗口只有6道。这就是问题所在——题量和覆盖面之间没有必然关系刷得多不等于刷得全更不等于每一类都到了能盲写的程度。中段疲劳期有几个很典型的信号我对了一下几乎全中打开题目先看标签看到简单才敢点看到困难直接跳。一道题写出来能过样例但不敢提交反复改边界。看题解时觉得哦原来是这样关掉页面自己写卡在同一个位置。错题本越记越厚但从来没回头翻过第二遍。单日题量从5题掉到2题但耗时反而变长了。这些症状的共同点不是能力不够而是没有把已经会的东西固化成可复用的模板。人的短期记忆能扛住几十道题的细节扛不住两百道。到了第73天细节必须外置到笔记和模板里脑子腾出来处理真正的新问题。1.2 用套路指纹给题目归类我之前的分类方式是按题库标签走数组、字符串、动态规划、图论。这个分类对新手友好但到了中后期就失效了——因为同一道题往往同时挂着三四个标签最长递增子序列是动态规划也是二分课程表是图论也是拓扑排序。按标签复习等于每道题复习三遍效率极低。后来我换成按套路指纹归类。所谓套路指纹就是这道题的解法骨架里最不可替换的那一步操作。比如套路指纹核心操作典型题有序区间收缩用 mid 把区间劈成两半并丢弃一边搜索旋转数组、寻找峰值答案单调性判定猜测答案后写 check 函数分割数组的最大值、爱吃香蕉的珂珂双指针同向左右指针都不回退长度最小的子数组、无重复字符最长子串单调栈入栈前弹掉破坏单调性的元素每日温度、柱状图中最大矩形状态压缩搜索用位掩码表示已选集合全排列、旅行商简化版图上分层扩展按距离或权值顺序出队最短路、最小生成树、多源扩散按指纹归类之后复习单位从一道题变成了一类骨架。第73天我把187道题压成了23个指纹每个指纹挑2到3道代表题一周只复这50道左右剩下的全部归档。这个压缩比例看起来激进但一周之后我盲写二分的正确率从六成到了九成以上。1.3 一张我自己在用的题单归档表归档这一步很关键因为它决定了你三个月后还能不能找回当时的思路。我的表长这样字段不多但每个都必要字段记录内容为什么需要题目名原始题名方便回查套路指纹上面那套分类复习单位关键卡点第一次没写出来的具体原因最值钱的字段我的模板版本最终定稿的代码直接复用复杂度时间/空间判断能不能过数据范围复习日期第一次、第三次、第七天间隔复习其中关键卡点这个字段我写得最狠。不是写二分边界没处理好这种废话而是写当 target 不存在时我返回的是 lo但 lo 可能等于 n越界了。这种颗粒度的记录复习的时候一眼就能回忆起当时的思维漏洞。提示归档表不要放在云端笔记里就完事一定要导出成能被搜索的纯文本。我试过用在线表格结果断网时什么也查不到最后改成 Markdown 文件放在本地目录用命令行搜索效率高得多。2. 二分查找写对不难写不挂才难2.1 区间定义决定循环条件和收缩方式二分是刷题路上最典型的看起来最简单、错起来最离谱的算法。我统计过自己前70天的提交记录二分相关的题目里第一次提交通过率只有五成出头比动态规划还低。原因几乎是同一个区间定义和收缩方式不匹配。二分的所有混乱都来自一个问题你的搜索区间到底是[lo, hi]还是[lo, hi)这两个定义决定了三件事——hi的初始值、循环条件、以及收缩时边界怎么动。这三件事必须成套出现混用任何一个都会翻车。我把两个版本并排放一下项目左闭右闭[lo, hi]左闭右开[lo, hi)hi 初值n - 1n循环条件lo hilo hi收缩写法lo mid1 / hi mid-1lo mid1 / hi mid循环结束lo hi区间空lo hi区间剩一个空闲变量无无关键点在于区间必须始终包含候选答案。左闭右闭版本里mid已经被检查过了所以两边都要±1把它排除左闭右开版本里hi本身不在区间内所以收缩到mid就刚刚好。我个人的做法是固定只用左闭右开。理由是它的循环不变量更干净[0, lo)永远全是确定不满足的[hi, n)永远全是确定满足的循环结束时lo就是第一个满足条件的位置。这个说法在找边界类题目上特别省心。2.2 我固定下来的三套模板三套模板覆盖我遇到的绝大部分场景背下来之后基本不用再推导。第一套精确查找。int binarySearch(vectorint a, int target) { int lo 0, hi a.size(); // [lo, hi) while (lo hi) { int mid lo (hi - lo) / 2; if (a[mid] target) lo mid 1; else hi mid; } return (lo (int)a.size() a[lo] target) ? lo : -1; }注意这里返回的是第一个大于等于 target 的位置精确查找只是在它外面加了一层判断。mid lo (hi - lo) / 2这个写法不是洁癖是为了防止lo hi溢出虽然 Python 不需要但换成 C 或 Java 就是必备习惯。第二套找最后一个满足条件的位置。int lastTrue(vectorint a, int target) { int lo 0, hi a.size(); // 找最后一个 target while (lo hi) { int mid lo (hi - lo 1) / 2; // 上取整 if (a[mid] target) lo mid; else hi mid - 1; } return lo; }这一套的关键是(hi - lo 1) / 2这个上取整。为什么因为当hi lo 1时下取整会让mid lo如果分支走的是lo mid区间大小不变直接死循环。上取整保证mid lo区间一定收缩。第三套答案二分。int solve(int n) { int lo 下界, hi 上界; // lo 一定不可行hi 一定可行 while (lo hi) { int mid lo (hi - lo) / 2; if (check(mid)) hi mid; // 找最小可行解 else lo mid 1; } return lo; }答案二分的难点不在框架在check函数和上下界。上下界要保证lo 一定不可行、hi 一定可行否则返回的可能是伪造的最优解。我踩过一次题目要求最小速度我把下界设成了 0结果check(0)会因为除零直接崩改成 1 才正常。2.3 旋转数组与答案二分两种高频变形旋转数组是二分里最反直觉的一类。核心观察是即使数组被旋转过a[mid]和a[lo]比较之后总有一半是有序的。判断哪一半有序就在那一半里判断 target 是否落在区间内然后决定往哪边收。int searchRotated(vectorint a, int target) { int lo 0, hi a.size() - 1; while (lo hi) { int mid lo (hi - lo) / 2; if (a[mid] target) return mid; if (a[lo] a[mid]) { // 左半有序 if (a[lo] target target a[mid]) hi mid - 1; else lo mid 1; } else { // 右半有序 if (a[mid] target target a[hi]) lo mid 1; else hi mid - 1; } } return -1; }这里有个必须注意的细节判断左半有序用的是a[lo] a[mid]而不是。因为当lo mid时区间只剩两个元素a[lo] a[mid]这时候左半是有序的用严格小于会把它误判成右半有序然后在错误的区间里收缩。答案二分的典型形态是最大值最小化或最小值最大化。判断信号很明确题目里出现最小可能的最大值最大可能的最小值至少 k 个不超过 m这类措辞八成可以二分答案。写这类题的顺序应该是先确认答案有单调性答案越大越容易满足条件再写 check最后套框架。2.4 死循环和下标越界是怎么来的我在二分上踩过的坑归纳下来就四种每一种都对应一个具体的写法错误死循环区间大小恒为 1 时不收缩。根因是mid取整方向和收缩方向不匹配。找左边界时用下取整 hi mid找右边界时用上取整 lo mid。越界循环结束时直接用lo访问数组但lo可能等于 n。根因是没做返回前的合法性检查。漏解hi初值设成n - 1却在循环里用hi lo判断。根因是区间定义和循环条件混用。多解check(mid)里写了还是没想清楚导致返回的是边界旁边那个位置。根因是没区分第一个满足和最后一个满足。注意验证二分写法最快的方法不是看代码是拿长度为 0、1、2 的数组各跑一遍。这三种长度能触发几乎所有的边界 bug我现在的习惯是写完先手推这三个用例比肉眼看代码快三倍。3. 排序与堆从手写冒泡到直接用优先队列3.1 四种基础排序的实际取舍刚开始刷题那会儿看到排序题我会手写一遍冒泡或者选择排序觉得这样更懂原理。到第73天我的做法完全反过来了能调库就调库只在必须手写的时候才手写。原因很简单实战里没人在乎你会不会写冒泡在乎的是你的整体复杂度能不能过数据范围。但懂原理这件事依然重要因为它决定了你能不能选对工具。四种基础排序的实战定位差别很大算法平均时间最坏时间空间稳定性实战定位冒泡O(n²)O(n²)O(1)稳定只用来理解交换思想插入O(n²)O(n²)O(1)稳定小规模或近乎有序的数据归并O(n log n)O(n log n)O(n)稳定需要稳定 链表场景快排O(n log n)O(n²)O(log n)不稳定通用首选注意三数取中选的时候先问两个问题数据规模多大、需不需要稳定。规模小于几十插入排序反而比快排快因为没有递归开销规模上百万又不要求稳定快排是首选要求稳定就用归并或者直接调库的稳定排序。算法题里更常见的其实是第三问这道题真的需要完整排序吗。TopK、中位数、第 k 小这类问题完整排序是浪费用堆或者快速选择能降到 O(n log k) 甚至期望 O(n)。3.2 topK 问题为什么堆比快排更稳TopK 问题的两种主流解法我都写过实测下来堆更值得背。解法一小顶堆维护 k 个元素。int findKthLargest(vectorint nums, int k) { priority_queueint, vectorint, greaterint pq; // 小顶堆 for (int x : nums) { pq.push(x); if ((int)pq.size() k) pq.pop(); } return pq.top(); }思路是堆里始终保留当前见过的最大 k 个元素堆顶是这 k 个里最小的也就是第 k 大。时间复杂度 O(n log k)空间 O(k)。数据是流式到达的时候这个解法几乎是唯一选择因为你没法对未知长度的流做快排。解法二快速选择。int partition(vectorint a, int lo, int hi) { int pivot a[hi]; int i lo; for (int j lo; j hi; j) if (a[j] pivot) swap(a[i], a[j]); swap(a[i], a[hi]); return i; }每次分区只递归一边期望时间 O(n)。问题在于最坏情况是 O(n²)而构造最坏用例的方法在刷题网站上是公开的所以快速选择在生产代码里通常要加随机化或者三数取中。算法题里能用但我会优先写堆因为它的复杂度上界是确定的不容易被特殊用例针对。3.3 堆排序的建堆与下沉细节写堆排序的时候有两个容易糊的地方。第一个是建堆的顺序。从n/2 - 1开始往前下沉而不是从 0 开始往后。原因是完全二叉树的下标大于n/2 - 1的节点全是叶子叶子本身就是合法堆不需要处理。从后往前下沉能保证每个节点下沉时它的左右子树已经是堆了这就是自底向上建堆能在 O(n) 完成的原理。void siftDown(vectorint a, int n, int i) { while (true) { int largest i, l 2 * i 1, r 2 * i 2; if (l n a[l] a[largest]) largest l; if (r n a[r] a[largest]) largest r; if (largest i) break; swap(a[i], a[largest]); i largest; } } void heapSort(vectorint a) { int n a.size(); for (int i n / 2 - 1; i 0; --i) siftDown(a, n, i); // 建堆 O(n) for (int i n - 1; i 0; --i) { swap(a[0], a[i]); siftDown(a, i, 0); } }第二个是排序阶段的下沉范围。每次把堆顶换到末尾之后堆的有效长度减一下沉的时候必须传新的长度i否则会把已经排好的元素重新搅进去。3.4 稳定性这个隐藏参数稳定性很容易被忽略直到它咬你一口。多关键字排序是最典型的场景先按分数排分数相同再按姓名排。如果排序不稳定第二次排序会打乱第一次的顺序。刷题里遇到稳定需求最省事的做法是把比较函数写成多关键字比较一次排序搞定而不是依赖排序算法本身的稳定性。因为 C 的std::sort是不稳定的Java 的Arrays.sort对基本类型也不稳定只有 Python 的sorted和 Java 的对象数组排序是稳定的。跨语言写题的时候这条差异很容易让人翻车。提示Python 里做多关键字排序技巧是用元组把需要反向的字段取负号。比如按分数降序、姓名升序排就写sorted(people, keylambda x: (-x.score, x.name))比自定义比较函数快得多也不会踩稳定性的坑。4. KMPnext 数组到底在跳过什么4.1 暴力匹配重复比较在哪字符串匹配最初的写法是双循环主串从每个位置起模式串逐字符比对。它的时间最坏是 O(nm)浪费在哪儿浪费在主串指针回退。每次失配之后主串指针要退回本轮起点的下一个位置但前面已经比对成功的那一段信息被完全丢掉了。举个具体例子主串是aaaaab模式串是aaab。前三个字符全匹配第四个失配。暴力解法会把主串指针挪到第二位重新比三个 a。但实际上我们通过刚才的比较已经知道前三个都是 a第二位起始的匹配情况是可以直接推出来的不需要重新比。KMP 的全部贡献就是把这份信息变成next数组让主串指针永不回退。4.2 前缀函数的推导过程next数组更准确的说法是前缀函数的定义是对于模式串的每个前缀p[0..i]找出它的最长相等真前后缀的长度。真前后缀的意思是前缀和后缀都不能是整个字符串本身。比如abab的最长相等真前后缀是ab长度 2。为什么这个长度有用因为当在位置i失配时我们已经知道p[0..i-1]这一段是完全匹配的。如果这段有个长度为k的相等前后缀那就意味着后缀那部分在主串里已经匹配上的等于前缀那部分所以模式串可以直接滑到前缀的位置继续比不需要回退主串指针。推导过程用一个循环就能算完核心是复用前一位的结果vectorint prefixFunction(const string p) { int n p.size(); vectorint pi(n, 0); for (int i 1; i n; i) { int j pi[i - 1]; // 先拿前一位的答案 while (j 0 p[i] ! p[j]) j pi[j - 1]; // 不匹配就往前跳 if (p[i] p[j]) j; pi[i] j; } return pi; }那个while循环是很多人卡住的地方。它的含义是当前候选长度j对不上就退而求其次看有没有更短的相等前后缀。pi[j-1]正好就是长度为 j 的那个前缀的最长相等前后缀长度所以直接跳过去就行。这个跳转链的均摊复杂度是 O(n)因为j每次最多加 1跳转的总次数不会超过增加的总次数。4.3 手写 KMP 的三段式记忆我背 KMP 用的是三段式求 next、跑主串、错一位对齐。int kmpSearch(const string s, const string p) { if (p.empty()) return 0; vectorint pi prefixFunction(p); int j 0; // 模式串已匹配长度 for (int i 0; i (int)s.size(); i) { while (j 0 s[i] ! p[j]) j pi[j - 1]; if (s[i] p[j]) j; if (j (int)p.size()) return i - j 1; // 全匹配 } return -1; }第一段求 next 是自匹配第二段是在主串上匹配逻辑几乎一样唯一的区别是第二段多了个匹配成功就返回的判断。第三段是很多人会忘的返回的下标是i - j 1不是i因为j是模式串长度i是主串上最后一个匹配字符的位置。4.4 什么时候用哈希、什么时候用 KMPKMP 不是银弹。如果你只是想知道模式串有没有出现过字符串哈希的写法短得多常数也小// 滚动哈希预处理前缀哈希O(1) 取任意子串哈希 unsigned long long h[N], pw[N]; unsigned long long subHash(int l, int r) { // 闭区间 [l, r] return h[r 1] - h[l] * pw[r - l 1]; }哈希的优势是可以在 O(1) 内比较任意两段子串适合判断所有长度是否出现统计重复子串这类问题。缺点是可能碰撞需要用双模数或者随机基数降低概率。KMP 的优势是确定性没有任何概率成分而且能直接给出所有匹配位置。选择标准很简单需要拿到所有匹配位置或者题目明确卡常数用 KMP只是做存在性判断或者子串比较用哈希。5. 图论三件套Prim、Dijkstra、匈牙利各打各的仗5.1 建图前先问自己三个问题图论题的错误八成出在建图阶段而不是算法阶段。我现在的习惯是拿到题先问三句有向还是无向无向边要建两条只建一条会漏掉反向路径表现是答案偏大。边权是正是负有负权就不能用 Dijkstra得换 Bellman-Ford 或者 SPFA。求的是最短路径还是最小生成树这两个问题的答案往往不一样题目措辞要读准。建图方式上邻接表是默认选择。稠密图边数接近 n²可以用邻接矩阵但刷题里更常见的是稀疏图。链式前向星在 C 里能省内存但可读性差除非卡内存不然不推荐。5.2 Dijkstra 的贪心前提与堆优化Dijkstra 的核心是贪心每次从未确定的点里挑当前距离最小的那个确定下来。这个贪心成立的前提是所有边权非负。为什么因为如果存在负边那么当前距离最小这个点之后还可能通过负边变短你提前确定它就错了。堆优化版本的复杂度是 O((n m) log n)vectorlong long dijkstra(int n, vectorvectorpairint,int g, int s) { const long long INF LLONG_MAX / 4; vectorlong long dist(n, INF); priority_queuepairlong long,int, vectorpairlong long,int, greater pq; dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; // 过期条目跳过 for (auto [v, w] : g[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } return dist; }if (d dist[u]) continue;这一行必须有。它的作用是丢弃堆里的历史条目——同一个点可能被多次入堆只有最新那次的距离是有效的。少了这一行算法可能对同一个点重复松弛虽然答案不一定错但复杂度会被拖垮而且遇到有环图可能死循环。INF取LLONG_MAX / 4而不是LLONG_MAX是为了防止松弛时dist[u] w溢出变成负数。这个细节在 C 里是必须的用INT_MAX做距离时更明显INT_MAX 1直接变负数。5.3 Prim 与 Kruskal 的分工最小生成树的两个主流算法选择标准很清晰边少用 Kruskal点少用 Prim。更进一步说Kruskal 需要排序所有边复杂度 O(m log m)Prim 用堆优化是 O(m log n)。稠密图上 m 接近 n²Kruskal 的排序开销会明显大。Prim 的写法和 Dijkstra 极像区别只在更新条件long long prim(int n, vectorvectorpairint,int g) { vectorint dist(n, INT_MAX), vis(n, 0); priority_queuepairint,int, vectorpairint,int, greater pq; dist[0] 0; pq.push({0, 0}); long long total 0; int used 0; while (!pq.empty() used n) { auto [d, u] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] 1; total d; used; for (auto [v, w] : g[u]) if (!vis[v] w dist[v]) { // 注意这里是 w不是 dist[u]w dist[v] w; pq.push({dist[v], v}); } } return used n ? total : -1; // 不连通返回 -1 }最容易错的一行就是注释那句Dijkstra 松弛的是dist[u] w累加路径Prim 松弛的是w单条边权。因为 Prim 维护的是点到生成树的最短边不是到起点的距离。我第一次写的时候直接复制了 Dijkstra 的松弛式样例过了因为样例是个等边权图换到加权图上答案就偏大。5.4 匈牙利算法的增广路直觉二分图最大匹配用匈牙利算法本质是不断找增广路。增广路的直觉可以这样理解你要给一个还没配对的左点找工作敲开一个右点如果它已经被占了就去问占它的那个左点能不能换一个能换就腾出来换不了就继续往下问。bool dfs(int u, vectorvectorint g, vectorint matchR, vectorint vis) { for (int v : g[u]) { if (vis[v]) continue; vis[v] 1; if (matchR[v] -1 || dfs(matchR[v], g, matchR, vis)) { matchR[v] u; return true; } } return false; } int hungarian(int nLeft, int nRight, vectorvectorint g) { vectorint matchR(nRight, -1); int res 0; for (int u 0; u nLeft; u) { vectorint vis(nRight, 0); // 每个左点重新清空访问标记 if (dfs(u, g, matchR, vis)) res; } return res; }vis数组的作用是防止在递归里绕圈。它必须在每个左点的外层循环里清空因为一次增广过程内部的访问标记不能跨轮复用。这个清空位置每年都在坑人我见过不少人把它开在函数外面忘了重置结果匹配数偏小。5.5 从判题错误反推建图错误图论题报错的时候看错误类型就能大致定位问题判题结果常见原因答案偏大无向边只建了一条或漏了自环处理答案偏小边权累加溢出或距离初值设太小部分用例超时用了邻接矩阵或者缺了过期条目跳过死循环堆优化缺vis判断或有负权导致反复松弛结果不稳定用了哈希且基数固定被特殊数据卡碰撞这套对照表帮我省了很多调试时间。现在我提交图论题之前会先扫一眼这五项尤其是无向边建图和距离初值这两个。6. 贪心与剪枝跳跃游戏 II 的最远可达视角6.1 贪心需要证明不是感觉贪心是刷题里最容易被滥用的思想。写不出动态规划的时候很多人会想那我贪一下吧结果在某个用例上翻车。判断贪心能不能用标准只有一个局部最优能不能推出全局最优。这个东西必须能证明哪怕证明不是写进代码里的脑子里也得过一遍。跳跃游戏 II 是个很典型的例子给定数组每个位置表示能跳的最大步数求跳到末尾的最少跳跃次数。贪心策略是在当前能到达的范围里选择能跳到最远的那个位置作为下一次落点。为什么这个贪心对因为跳跃次数是按层递增的第 k 次跳跃能覆盖的范围是一个区间你想让总次数最少就要让每一层覆盖得尽可能远。这个可以用交换论证说明假设最优解在第 k 跳选了位置 a而你选的是能跳更远的 b那么从 b 出发到达的所有位置从 a 出发也能到达因为 b 的可达范围包含 a 的所以换成 b 不会让答案变差。int jump(vectorint nums) { int n nums.size(); int jumps 0, curEnd 0, farthest 0; for (int i 0; i n - 1; i) { // 注意是 n-1 farthest max(farthest, i nums[i]); if (i curEnd) { // 到达当前层边界 jumps; curEnd farthest; // 开启下一层 } } return jumps; }循环上界是n - 1而不是n因为站在最后一个位置上时不需要再跳。这个一行的差异会让某些用例的答案多 1我第一次写就错在这。curEnd记录当前这一跳能覆盖的最右边界farthest记录下一跳能覆盖的最右边界当扫描到curEnd时说明当前这一跳用完了必须再跳一次。6.2 三种该剪枝的信号剪枝属于搜索题的必修课。回溯、DFS 这类搜索不加剪枝的复杂度通常是指数级的加了之后往往能过。我判断该不该剪枝的标准是三个信号搜索树的某个分支注定无解。比如组合求和里当前和已经超过目标值后面全是正数那这个分支可以直接砍。某个分支的结果一定比别人差。最优化问题里的下界/上界估计如果当前代价已经超过已知最优解就不用往下走了。同一状态重复出现。这时候不是剪枝的问题了是该上记忆化搜索或者动态规划。剪枝的顺序也有讲究先剪最便宜、砍掉最多的那一个。比如先按可行性剪越界、超和再做最优性剪。因为可行性判断通常是 O(1) 的最优性判断可能要做点计算。6.3 回溯题里剪枝的收益有多大拿最经典的组合求和举个例子不加剪枝的写法void dfs(vectorint c, int target, int start, vectorint path, vectorvectorint res) { if (target 0) { res.push_back(path); return; } if (target 0) return; // 可行性剪枝 for (int i start; i (int)c.size(); i) { if (c[i] target) break; // 排序后的最优性剪枝 path.push_back(c[i]); dfs(c, target - c[i], i, path, res); path.pop_back(); } }第二行的target 0是可行性剪枝c[i] target配合提前排序是另一层剪枝。这两个加起来的收益有多大我实测了一组数据候选数组长度 30目标和 500不剪枝的版本跑了将近 40 秒还没出结果加上这两行之后 0.3 秒内完成。原因就是候选值大于剩余目标时整个后续子树都是废的而排序让这个判断变成一个break直接砍掉整条分支。注意break的前提是数组已经升序排列。如果数组没排序必须用continue否则会漏解。这个错误非常隐蔽因为小程序例往往恰好能过。7. 第73天之后的节奏调整与扩展方向调整完分类方式之后我把每天的练习拆成了固定结构新题 2 道、回刷 3 道、纯默写 1 道。新题选当前最弱的指纹类型回刷选三天前和七天前的题默写是从归档表里随机抽一道不看任何资料直接手写完整代码。默写这一步最折磨人但收益最高因为它直接检验我到底是真会还是看着眼熟。复盘比例上我现在的习惯是练习和复盘按 1:1 分配。以前觉得复盘浪费时间后来发现不复盘的代价更大同一类错误能连着犯四五天因为每次都是写出来、错了、改对、下一题没有停下来想我为什么会写错。复盘不需要很长每天二十分钟把当天的卡点写进归档表然后对着指纹清单扫一遍看看有没有能合并的模板。错题本的写法我调过三次。最早的版本是抄题解抄完就忘第二版是记题目和错误类型效果一般现在这一版只记三样东西——我当时是怎么想的、正确思路是怎么想的、两者的分叉点在哪。第三样最关键因为分叉点才是真正的知识缺口。比如有一道题我一直在用 BFS 做最短路但边权不是 1分叉点就在BFS 只能处理无权图或等权图这条前提上。把这条写下来后面遇到类似题就不用再撞一次。再往后走纯刷题能带来的边际收益会越来越小。我打算在保持每日量的同时往工程算法方向延伸一点数据处理类DBSCAN 这类基于密度的聚类实现起来比想象中简单核心只有邻域查询和簇扩展两步但对距离度量和参数很敏感。优化类模拟退火、粒子群这类启发式算法思路和刷题的贪心完全不同它们不保证最优靠随机性和迭代次数逼近好解适合用来开阔视野。特征筛选类mRMR 这类基于互信息的特征选择方法工程里用得多理解它需要一点概率基础但拆开看就是相关性和冗余度的权衡。路径搜索类双向 BFS、A* 这类带启发式的搜索在网格地图上比朴素 BFS 快一个量级思路和跳跃游戏的贪心层扩展是相通的。这些方向不需要立刻全上挑一个和当前工作相关的切入就行。刷题提供的是算法直觉和调试能力工程算法提供的是把直觉落到具体数据和约束上的经验两者互补。第73天那二十分钟的空白期现在回头看反而是个转折点。前面靠热情推着走后面得靠系统推着走。把题目按指纹压缩、把模板固化成代码、把卡点写进归档表这三件事做完之后题单从187道变成了50道高频正确率反而涨了。如果你也在六七十天这个位置卡着不妨先停一天把手上所有题重新读一遍标签看看哪些类型的题你已经两个月没碰过了。