第73天，我在题单页面停了二十分钟，一道都没点进去。桌面右下角的计时器还在跳，昨天那道"搜索旋转排序数组"的最后一组边界用例又浮上来——不是不会，是写完之后我自己都不确定它到底对不对。这个状态在刷题的前两个月从没出现过，前面每一天都是新题、新知识点、新成就感，到了第73天，题目开始长得越来越像，错误却开始藏得越来越深。

这篇记录想聊的不是"第73天我刷了哪几道题"，而是刷到这个阶段之后，练习方式本身该怎么调。如果你刚起步，这里面的模板和口诀可以直接抄；如果你也卡在六七十天这个区间，觉得题目都见过但正确率上不去，那大概能省你几周的摸索。算法刷题这件事，前30天拼的是能不能看懂题解，30到70天拼的是能不能独立写出来，70天往后拼的东西完全换了——是稳定性、是分类能力、是对"我这个写法为什么对"的确定感。下面按我这几天的实际复盘顺序展开，从二分开始，到字符串、图论、贪心剪枝，最后说说节奏怎么改。

1. 第73天我停了两个小时，只为把题单重新排一遍

1.1 中段疲劳期的真实症状

标题叫"刷题记录"，但真正值得记下来的从来不是"今天AC了3题"这种流水账。第73天我做了一件看起来很像偷懒的事：把过去72天做过的187道题重新过了一遍标签，结果发现自己有41道题在"二分答案"这一类上，而"滑动窗口"只有6道。这就是问题所在——题量和覆盖面之间没有必然关系，刷得多不等于刷得全，更不等于每一类都到了能盲写的程度。

中段疲劳期有几个很典型的信号，我对了一下，几乎全中：

• 打开题目先看标签，看到"简单"才敢点，看到"困难"直接跳。
• 一道题写出来能过样例，但不敢提交，反复改边界。
• 看题解时觉得"哦原来是这样"，关掉页面自己写，卡在同一个位置。
• 错题本越记越厚，但从来没回头翻过第二遍。
• 单日题量从5题掉到2题，但耗时反而变长了。

这些症状的共同点不是"能力不够"，而是没有把已经会的东西固化成可复用的模板。人的短期记忆能扛住几十道题的细节，扛不住两百道。到了第73天，细节必须外置到笔记和模板里，脑子腾出来处理真正的新问题。

1.2 用"套路指纹"给题目归类

我之前的分类方式是按题库标签走：数组、字符串、动态规划、图论。这个分类对新手友好，但到了中后期就失效了——因为同一道题往往同时挂着三四个标签，"最长递增子序列"是动态规划也是二分，"课程表"是图论也是拓扑排序。按标签复习，等于每道题复习三遍，效率极低。

后来我换成按"套路指纹"归类。所谓套路指纹，就是这道题的解法骨架里最不可替换的那一步操作。比如：

按指纹归类之后，复习单位从"一道题"变成了"一类骨架"。第73天我把187道题压成了23个指纹，每个指纹挑2到3道代表题，一周只复这50道左右，剩下的全部归档。这个压缩比例看起来激进，但一周之后我盲写二分的正确率从六成到了九成以上。

1.3 一张我自己在用的题单归档表

归档这一步很关键，因为它决定了你三个月后还能不能找回当时的思路。我的表长这样，字段不多，但每个都必要：

其中"关键卡点"这个字段我写得最狠。不是写"二分边界没处理好"这种废话，而是写"当 target 不存在时，我返回的是 lo，但 lo 可能等于 n，越界了"。这种颗粒度的记录，复习的时候一眼就能回忆起当时的思维漏洞。

提示：归档表不要放在云端笔记里就完事，一定要导出成能被搜索的纯文本。我试过用在线表格，结果断网时什么也查不到，最后改成 Markdown 文件放在本地目录，用命令行搜索，效率高得多。

2. 二分查找：写对不难，写不挂才难

2.1 区间定义决定循环条件和收缩方式

二分是刷题路上最典型的"看起来最简单、错起来最离谱"的算法。我统计过自己前70天的提交记录，二分相关的题目里，第一次提交通过率只有五成出头，比动态规划还低。原因几乎是同一个：区间定义和收缩方式不匹配。

二分的所有混乱都来自一个问题：你的搜索区间到底是[lo, hi]还是[lo, hi)？这两个定义决定了三件事——hi的初始值、循环条件、以及收缩时边界怎么动。这三件事必须成套出现，混用任何一个都会翻车。

我把两个版本并排放一下：

关键点在于：区间必须始终包含候选答案。左闭右闭版本里，mid已经被检查过了，所以两边都要±1把它排除；左闭右开版本里，hi本身不在区间内，所以收缩到mid就刚刚好。

我个人的做法是固定只用左闭右开。理由是它的循环不变量更干净：[0, lo)永远全是"确定不满足"的，[hi, n)永远全是"确定满足"的，循环结束时lo就是第一个满足条件的位置。这个说法在找边界类题目上特别省心。

2.2 我固定下来的三套模板

三套模板覆盖我遇到的绝大部分场景，背下来之后基本不用再推导。

第一套：精确查找。

int binarySearch(vector<int>& 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(vector<int>& 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(vector<int>& 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天我的做法完全反过来了：能调库就调库，只在必须手写的时候才手写。原因很简单，实战里没人在乎你会不会写冒泡，在乎的是你的整体复杂度能不能过数据范围。

但"懂原理"这件事依然重要，因为它决定了你能不能选对工具。四种基础排序的实战定位差别很大：

选的时候先问两个问题：数据规模多大、需不需要稳定。规模小于几十，插入排序反而比快排快，因为没有递归开销；规模上百万又不要求稳定，快排是首选；要求稳定就用归并或者直接调库的稳定排序。算法题里更常见的其实是第三问：这道题真的需要完整排序吗。TopK、中位数、第 k 小这类问题，完整排序是浪费，用堆或者快速选择能降到 O(n log k) 甚至期望 O(n)。

3.2 topK 问题为什么堆比快排更稳

TopK 问题的两种主流解法我都写过，实测下来堆更值得背。

解法一：小顶堆维护 k 个元素。

int findKthLargest(vector<int>& nums, int k) { priority_queue<int, vector<int>, greater<int>> 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(vector<int>& 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(vector<int>& 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(vector<int>& 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, key=lambda x: (-x.score, x.name))，比自定义比较函数快得多，也不会踩稳定性的坑。

4. KMP：next 数组到底在"跳过"什么

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的相等前后缀，那就意味着后缀那部分（在主串里已经匹配上的）等于前缀那部分，所以模式串可以直接滑到前缀的位置继续比，不需要回退主串指针。

推导过程用一个循环就能算完，核心是"复用前一位的结果"：

vector<int> prefixFunction(const string& p) { int n = p.size(); vector<int> 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; vector<int> 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 什么时候用哈希、什么时候用 KMP

KMP 不是银弹。如果你只是想知道模式串有没有出现过，字符串哈希的写法短得多，常数也小：

// 滚动哈希：预处理前缀哈希，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)：

vector<long long> dijkstra(int n, vector<vector<pair<int,int>>>& g, int s) { const long long INF = LLONG_MAX / 4; vector<long long> dist(n, INF); priority_queue<pair<long long,int>, vector<pair<long 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, vector<vector<pair<int,int>>>& g) { vector<int> dist(n, INT_MAX), vis(n, 0); priority_queue<pair<int,int>, vector<pair<int,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, vector<vector<int>>& g, vector<int>& matchR, vector<int>& 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, vector<vector<int>>& g) { vector<int> matchR(nRight, -1); int res = 0; for (int u = 0; u < nLeft; ++u) { vector<int> vis(nRight, 0); // 每个左点重新清空访问标记 if (dfs(u, g, matchR, vis)) ++res; } return res; }

vis数组的作用是防止在递归里绕圈。它必须在每个左点的外层循环里清空，因为一次增广过程内部的访问标记不能跨轮复用。这个清空位置每年都在坑人，我见过不少人把它开在函数外面忘了重置，结果匹配数偏小。

5.5 从判题错误反推建图错误

图论题报错的时候，看错误类型就能大致定位问题：

这套对照表帮我省了很多调试时间。现在我提交图论题之前，会先扫一眼这五项，尤其是无向边建图和距离初值这两个。

6. 贪心与剪枝：跳跃游戏 II 的"最远可达"视角

6.1 贪心需要证明，不是感觉

贪心是刷题里最容易被滥用的思想。写不出动态规划的时候，很多人会想"那我贪一下吧"，结果在某个用例上翻车。判断贪心能不能用，标准只有一个：局部最优能不能推出全局最优。这个东西必须能证明，哪怕证明不是写进代码里的，脑子里也得过一遍。

跳跃游戏 II 是个很典型的例子：给定数组，每个位置表示能跳的最大步数，求跳到末尾的最少跳跃次数。贪心策略是"在当前能到达的范围里，选择能跳到最远的那个位置作为下一次落点"。

为什么这个贪心对？因为跳跃次数是按层递增的，第 k 次跳跃能覆盖的范围是一个区间，你想让总次数最少，就要让每一层覆盖得尽可能远。这个可以用交换论证说明：假设最优解在第 k 跳选了位置 a，而你选的是能跳更远的 b，那么从 b 出发到达的所有位置，从 a 出发也能到达（因为 b 的可达范围包含 a 的），所以换成 b 不会让答案变差。

int jump(vector<int>& 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(vector<int>& c, int target, int start, vector<int>& path, vector<vector<int>>& 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道高频，正确率反而涨了。如果你也在六七十天这个位置卡着，不妨先停一天，把手上所有题重新读一遍标签，看看哪些类型的题你已经两个月没碰过了。