算法设计与分析这门课，期末复习的时候最折磨人的地方在于：课本上的定理证明看起来都懂，一到手写代码和推导复杂度就卡壳；复习题刷了一堆，考试换个包装又不认识了。我带过几届学弟学妹复习，也自己踩过各种坑，最后总结出一套还算好用的打法——不追求把整本书背下来，而是抓住"复杂度分析 + 五大算法思想 + 图论 + 字符串"这几根主线，把每类题目的模板、证明套路和易错点固化下来。这篇内容就是把这套复盘思路完整摊开讲，从知识地图怎么画、每类算法的核心考点在哪、手写代码怎么保证不丢分，到考场上时间怎么分配，都尽量说到能直接照着用的程度。
不管你是刚学完一学期、脑子里还是一团浆糊，还是已经复习过一轮、想找地方查漏补缺，下面的内容都能对着看。核心关键词就两个：算法、算法设计与分析，我会围绕这门课期末最常考的题型来讲，代码以 C++ 和伪代码为主，因为我发现大部分学校的期末卷子还是这两种写法最吃香。
1. 复习前的整体打法与知识地图拆解
很多人复习算法第一反应是打开课本从第一章开始看，看到"算法的定义"就直接困了。我强烈建议别这么干。这门课的知识结构是网状的，第一章的定义、第二章的数学基础、后面的分治和动态规划其实是同一套东西在不同场景下的应用，你线性地看只会越看越乱。正确做法是先花半小时把整门课的知识地图画出来，知道每一块在考卷上大概占多少分，再决定投入多少精力。
1.1 先搞清楚考卷长什么样，再决定怎么复习
不同学校的卷子风格差异极大，有的偏证明、有的偏手写代码、有的偏选择填空。我统计过自己和几个朋友遇到的卷子，大致可以分成三类：第一类是"重推导型"，会有大量复杂度计算、递推式求解、正确性证明，手写代码题只有一两道；第二类是"重实现型"，选择填空加四到五道编程题，证明题基本没有，或者只要求说思路；第三类是"混合型"，各占一半。你先去找学长学姐要一份往年卷，判断自己属于哪一类，复习的重心就完全不一样了。
如果是重推导型，那你必须把主定理、递归树、交换论证这些证明工具练熟，代码能看懂就行；如果是重实现型，那就把每个经典算法的手写模板背到肌肉记忆，证明题只记住结论和一句话思路即可。最怕的是明明考重实现，你花三天啃NP完全性证明，最后编程题模板忘了，那就亏大了。这个判断我建议在第一轮复习开始前就做完，花不了多少时间，但能省下大量无效劳动。
提示：找往年卷的时候顺便把老师的出题习惯记下来——他是喜欢考书上原题，还是喜欢改参数、换场景。这两者的复习策略完全不同。
1.2 一张知识地图：从复杂度到 NP 完全性
把这门课拆开，主干其实就这么几块，我按考试出现频率排个序：
- 复杂度分析：渐进记号、递推式求解、最好/最坏/平均情况分析。几乎每张卷子都有，而且它是后面所有题的地基。
- 分治：归并排序、快速排序、二分查找、最大子段和、逆序对计数、大整数乘法。
- 动态规划：LCS、LIS、0-1背包、完全背包、编辑距离、矩阵连乘、区间DP。
- 贪心：活动安排、哈夫曼编码、单源最短路（Dijkstra 也有贪心思想）、跳跃游戏。
- 回溯与分支限界：N 皇后、子集和、装载问题、图的着色。
- 图算法：最短路（Dijkstra / Bellman-Ford / Floyd）、最小生成树（Prim / Kruskal）、拓扑排序、关键路径。
- 字符串：KMP 的 next 数组、简单模式匹配。
- NP 完全性：P、NP、NPC 的定义，归约的基本概念，一般只考概念题。
你会发现，分治、动态规划、贪心这三块本质上都是在回答同一个问题："怎么把大问题拆成小问题"，只是拆法和求解顺序不同。把这条线抓住，复习效率会高很多。
1.3 三轮复习法：时间怎么排最划算
我自己的实践是把复习分成三轮，每轮目标不同，具体安排如下表：
| 轮次 | 时间占比 | 核心目标 | 主要动作 |
|---|---|---|---|
| 第一轮 | 40% | 建立框架、补基础 | 过一遍知识地图，把每类算法的思想和模板抄一遍 |
| 第二轮 | 40% | 刷题、找漏洞 | 按题型分类刷题，错题单独整理 |
| 第三轮 | 20% | 模拟、固化模板 | 限时做往年卷，把代码模板默写到不看笔记 |
第一轮千万不要追求全都会，你的目标是"知道有这么个东西，知道它在哪一章"。第二轮才是真正长本事的时候，重点是分类刷题——同一类题连着做五道，比五类题各做一道效果好得多。第三轮就干一件事：默写模板，限时模拟。
注意：三轮不是严格分开的，第二轮的错题要回填到第一轮的框架里，第三轮发现模板记不住也要回头补。复习是个循环收敛的过程，别把它当成流水线。
2. 复杂度分析：所有题目的地基，先啃下这块硬骨头
复杂度分析是这门课里最"数学"的部分，也是很多人第一个卡壳点。但我要说句实在话，期末考试里的复杂度分析远没有课本写得那么吓人，翻来覆去就那几个套路。你只要把渐进记号的含义、递推式求解的三种方法、以及几类常见结构的复杂度算清楚，这一块基本可以拿满分。
2.1 渐进记号别死背定义，要会"看增长量级"
大 O、大 Ω、大 Θ 这三个记号，课本上的定义是用极限和常数写的，看着很唬人。其实你只要记住一句话：它们描述的不是"运行多少秒"，而是"当输入规模 n 变大时，运行时间的增长趋势"。大 O 是上界（最多这么快），大 Ω 是下界（至少这么快），大 Θ 是紧确界（差不多就这么快）。
举个生活化的例子：你请客吃饭，大 O 相当于"花销不超过 500 块"，大 Ω 相当于"至少花 200 块"，大 Θ 相当于"大概 300 到 350 之间"。考试常考的是给你两个函数，判断 f(n) = O(g(n)) 是否成立。这时候你不需要严格证明，直接看最高次项：n³ + 100n² 是 O(n³)，因为 n² 项在 n 变大后被 n³ 压住了。100n 是 O(n²)，也是 O(n³)，因为大 O 只要求上界，不要求最紧。
真正容易错的是对数。log n 比任何正的幂函数都慢，n log n 介于 n 和 n² 之间，这几个必须形成条件反射。还有一个坑：2^(2n) 和 2^n 是两个不同的量级，别以为底数不同无所谓——指数不同就是天壤之别，2^(2n) = (2^n)²，而常数底数不同（比如 2^n 和 3^n）在某些严格定义下确实是同量级，但考试一般不考这么细。
2.2 递推式求解三件套：代入法、递归树、主定理
递推式是复杂度分析的重头戏，比如 T(n) = 2T(n/2) + n 这种。求解方法有三种，我建议都掌握，因为题目有时会指定方法。
代入法（猜测 + 归纳证明）：先猜一个解，比如猜 T(n) = O(n log n)，然后假设对更小的规模成立，代入验证。这个方法考的是你的"数感"，猜的能力靠多做题积累。写的时候要注意归纳假设的严谨性，别跳步。
递归树法：把递归展开成一棵树，每一层的代价加起来。以 T(n) = 2T(n/2) + n 为例，第一层代价 n，第二层两个节点各 n/2、合计 n，第三层合计还是 n……一共有 log n 层，所以总代价是 n log n。这个方法特别直观，考试里画棵树 + 写几行求和就能拿分，性价比很高。
主定理（Master Theorem）：这是最省事的工具，形式是 T(n) = aT(n/b) + f(n)，比较 n^(log_b a) 和 f(n) 的大小：
- 如果 f(n) 比 n^(log_b a) 小（多项式级别），则 T(n) = Θ(n^(log_b a))；
- 如果两者同阶，则 T(n) = Θ(n^(log_b a) · log n)；
- 如果 f(n) 更大且满足正则条件，则 T(n) = Θ(f(n))。
拿归并排序举例，T(n) = 2T(n/2) + n，a=2，b=2，n^(log_2 2) = n，和 f(n) = n 同阶，所以 T(n) = Θ(n log n)。再拿二分查找举例，T(n) = T(n/2) + 1，a=1，b=2，n^(log_2 1) = n⁰ = 1，和 f(n)=1 同阶，所以 T(n) = Θ(log n)。这两个是最常考的，务必记牢。
注意：主定理有"空隙"，第一种和第三种情况之间如果 f(n) 不是多项式级别地大于或小于，主定理不适用，这时候得用递归树。考试里如果出了这种题，多半是老师想看你是否知道主定理的局限。
2.3 常考复杂度速查表：背下来能省一半时间
下面这张表是我复习时的"救命表"，考试前反复看，基本覆盖了所有会考的算法：
| 算法 | 最好 | 平均 | 最坏 | 空间 |
|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) |
| 二分查找 | O(1) | O(log n) | O(log n) | O(1) |
| Dijkstra（堆优化） | — | O((n+m) log n) | O((n+m) log n) | O(n+m) |
| Floyd | O(n³) | O(n³) | O(n³) | O(n²) |
| KMP | O(n+m) | O(n+m) | O(n+m) | O(m) |
快速排序最坏 O(n²) 这个点几乎年年考，原因也很清楚：当每次划分都极度不平衡（比如已经有序且总取第一个元素做基准）时，递归深度退化成 n。理解了这个原因，你就能顺带答出"随机化基准"或"三数取中"的优化方向。
3. 分治与排序类核心考点实战
分治是这门课里最"漂亮"的一类思想：把问题分成若干个规模更小的子问题，分别求解，再合并结果。听起来简单，但考试里的分治题往往在"合并"这一步做文章，合并写不好，分治就成了摆设。这一节把排序、查找和几个经典分治题讲清楚。
3.1 归并排序：先把模板刻在脑子里
归并排序是分治的标准范例，考试要求手写的时候，很多人卡在合并函数上。我把最稳的写法列出来，注意mid的取法、临时数组的边界、以及最后把剩余元素补进去的处理：
void mergeSort(vector<int>& a, int l, int r) { if (l >= r) return; int mid = l + (r - l) / 2; mergeSort(a, l, mid); mergeSort(a, mid + 1, r); vector<int> tmp; int i = l, j = mid + 1; while (i <= mid && j <= r) { if (a[i] <= a[j]) tmp.push_back(a[i++]); else tmp.push_back(a[j++]); } while (i <= mid) tmp.push_back(a[i++]); while (j <= r) tmp.push_back(a[j++]); for (int k = 0; k < tmp.size(); k++) a[l + k] = tmp[k]; }这里有几个细节值得强调。第一，mid = l + (r - l) / 2比(l + r) / 2更安全，虽然数组下标一般不会溢出，但养成习惯没坏处。第二，if (a[i] <= a[j])里的等号决定了排序的稳定性，归并排序是稳定排序，加等号才能保证相等元素保持原相对顺序，这个点经常出判断题。第三，复杂度 T(n) = 2T(n/2) + n，用主定理套出来是 Θ(n log n)，务必会推。
3.2 快速排序：划分是灵魂，复杂度过坑是重点
快速排序的代码比归并短，但细节更多，核心是划分（partition）。我用的是最经典的挖坑法（Hoare 划分的一个变体）：
int partition(vector<int>& a, int l, int r) { int pivot = a[l]; while (l < r) { while (l < r && a[r] >= pivot) r--; a[l] = a[r]; while (l < r && a[l] <= pivot) l++; a[r] = a[l]; } a[l] = pivot; return l; }划分完，基准左边的都不大于它，右边的都不小于它，然后递归处理左右两段。考试常问的坑有三个：为什么平均是 O(n log n)、为什么最坏是 O(n²)、为什么要随机化。平均情况的分析思路是：每次划分的位置是随机的，期望意义下左右两段规模比较均衡，递归深度 O(log n)，每层总代价 O(n)，合起来 O(n log n)。最坏情况就是每次都取到最大或最小值做基准，递归变成链状，深度 n，总代价 O(n²)。随机化的意义就是把"最坏情况"从必然变成概率极低，让期望复杂度稳定在 O(n log n)。
实操心得：手写快排的时候，
while里面的边界判断l < r一定不能丢，否则数组里有等于基准的元素时会死循环或者越界。这是我在纸上写代码时翻过车的地方。
3.3 二分查找的三种变体，别只会最基础那种
基础二分查找大家都熟，但考试往往考变体，比如"找第一个大于等于目标的位置"（lower_bound）和"找最后一个小于等于目标的位置"（upper_bound）。我建议直接记下面这个统一模板，它比各种花哨写法好记：
// 找第一个 >= target 的下标 int lowerBound(vector<int>& a, int target) { int l = 0, r = a.size(); // 注意 r 取 size，左闭右开 while (l < r) { int mid = l + (r - l) / 2; if (a[mid] < target) l = mid + 1; else r = mid; } return l; }这个模板的关键是区间定义成左闭右开[l, r)，循环条件是l < r，最后返回l。把<改成<=就能得到"找第一个大于 target"的位置。很多人记不住二分，是因为每次都用不同的区间定义，混着写必然出错。统一成一种，练熟就行。
分治经典题里，最大子段和和逆序对计数是高频考点。最大子段和的分治思路是：最大子段要么完全在左半边，要么完全在右半边，要么横跨中点。前两种递归求解，第三种从中点向两边扩展求最大值，然后三者取大。复杂度 T(n) = 2T(n/2) + O(n) = O(n log n)。逆序对计数则是在归并排序的合并过程中顺便统计：当右边的元素被取出时，左边剩下的元素个数就是它构成的逆序对数。这个技巧特别巧妙，理解了就忘不掉，而且它就是"归并排序的副产品"，代码改动极小。
4. 动态规划：状态定义定生死，转移方程见真章
动态规划是这门课最容易失分、也最能拉开差距的部分。我见过太多人，题目看懂了、思路也有了，但状态一写错，后面全盘皆输。这一节我把 DP 的通用解题流程拆开，再配合几道必考经典题。
4.1 动态规划四步法，照着走不会跑偏
我总结的 DP 四步法是这样的：
- 定义状态：明确
dp[i]或dp[i][j]到底表示什么。这一步是灵魂，写代码前先在纸上用一句话写清楚。 - 找转移方程：当前状态由哪些更小的状态推出来，怎么推。
- 确定边界和初始化：最小的子问题答案是什么，
dp数组初始值怎么设。 - 确定遍历顺序：保证算当前状态时，依赖的状态已经算好了。
这四步里，第一步最难也最关键。判断状态定义对不对有个简单标准：能不能从子问题的答案，唯一地推出当前答案。如果不能，说明状态维度不够，得加一维。
4.2 四道必考经典题，逐个击破
最长公共子序列（LCS）：给定两个字符串，求它们最长的公共子序列长度。状态定义dp[i][j]表示s1前 i 个字符和s2前 j 个字符的 LCS 长度。转移方程分两种情况：如果s1[i-1] == s2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1；否则dp[i][j] = max(dp[i-1][j], dp[i][j-1])。边界是dp[0][*] = dp[*][0] = 0。时间复杂度 O(nm)。
最长递增子序列（LIS）：经典做法是dp[i]表示以第 i 个元素结尾的最长递增子序列长度，转移是遍历所有j < i，若a[j] < a[i]则dp[i] = max(dp[i], dp[j] + 1)，复杂度 O(n²)。优化版用二分 + 贪心能做到 O(n log n)，考试如果没要求优化，写 O(n²) 就够了。
0-1 背包：dp[j]表示容量为 j 时能装的最大价值，转移是逆序遍历容量：dp[j] = max(dp[j], dp[j-w[i]] + v[i])。这里"逆序"是重点，因为要保证每个物品只被用一次。如果是完全背包（物品可以无限取），就改成顺序遍历，这个对比几乎是必考。
编辑距离：dp[i][j]表示把s1前 i 个字符变成s2前 j 个字符的最少操作数。转移考虑插入、删除、替换三种操作，取最小值。这道题的状态定义和 LCS 很像，可以一起记。
4.3 区间 DP 与滚动数组，进阶但常考
区间 DP 的典型是矩阵连乘和石子合并。状态一般是dp[i][j]表示区间[i, j]的最优解，转移是枚举分割点 k，dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost)。遍历顺序上，必须按区间长度从小到大来，因为长区间依赖短区间。
滚动数组则是空间优化的常用手法。当dp[i][j]只依赖dp[i-1][*]时，可以把第一维压掉，只留一维数组。0-1 背包就是典型例子。考试里如果能主动提出空间优化，往往是加分项。
注意：用滚动数组时一定要想清楚遍历方向。0-1 背包逆序、完全背包顺序，这个差别就是"物品能不能重复用"的直接体现，别记混了。
5. 贪心算法与正确性证明：选对策略，还要证明它对
贪心算法写起来最短，但它的"坑"在于——有时候贪心是错的，你得能判断出来。考试里贪心题的难点从来不是代码，而是"为什么这么贪是对的"，也就是正确性证明。
5.1 贪心的适用条件和两种证明套路
贪心能用的前提是问题具有两个性质：贪心选择性质（每一步的局部最优能导向全局最优）和最优子结构（大问题的最优解包含子问题的最优解）。证明局部最优能推出全局最优，常用两种方法：
交换论证法：假设存在一个最优解和贪心解在某一步不同，通过交换它们的某两个选择，证明交换后不会变差，从而说明"存在一个包含贪心选择的最优解"。这个证明写起来有固定套路，先设符号、再交换、最后说明不劣，练三五道就能上手。
归纳法：对步骤数做归纳，证明每一步之后贪心解都可以扩展成某个全局最优解。
5.2 三道经典贪心题，覆盖 90% 考法
活动安排问题：给定若干活动的起止时间，求最多能参加几个。贪心策略是"按结束时间从早到晚排序，能选就选"。为什么按结束时间排而不是开始时间？因为结束越早，留给后面活动的时间越多。这个"为什么"经常作为简答题考。
哈夫曼编码：每次从集合里取两个权值最小的节点合并，直到只剩一个。它保证加权路径长度最小，是贪心正确性的经典案例。手写的时候用优先队列（小顶堆）实现，复杂度 O(n log n)。
跳跃游戏 II：求跳到末尾的最少步数。贪心策略是"在当前能到达的范围内，选一个能跳最远的位置作为下一跳"。这道题在热词里也出现了，属于近年高频题，思路是维护当前步数能覆盖的最远边界，边界到了就步数加一。
5.3 贪心的常见误区，避开就是赚
最常见的误区是"看到最优化就上贪心"。最典型的反例是 0-1 背包——如果你按单位价值排序做贪心，会得到错误答案（因为物品不能拆分），正确解法是动态规划。这个对比是考试常考的概念题，一定要能举例说明。
第二个误区是"排序依据选错"。活动安排按结束时间，但有的题看着像活动安排，实际要按开始时间或者按区间长度，得具体分析。判断依据是：你的排序规则能否保证"不会因为当前选择而丢失更优的未来"。
第三个误区是证明写得太随意。考试里如果题目明确要求"证明贪心策略的正确性"，你光写"因为每次都选最优的所以全局最优"是拿不到分的，必须用交换论证或归纳法把逻辑走完。
6. 图算法高频考点：三大最短路 + 两棵生成树
图论部分的特点是算法多、细节杂，但每年考的其实就是那么几个。我把它拆成最短路、最小生成树、拓扑排序三条线来讲，每条线配上对比表和手写要点。
6.1 最短路三兄弟：Dijkstra、Bellman-Ford、Floyd 怎么选
这三个算法经常放在一起考，核心是"什么场景用哪个"。我整理成下面这张对比表：
| 算法 | 适用场景 | 负权边 | 复杂度 | 核心思想 |
|---|---|---|---|---|
| Dijkstra | 单源、非负权 | 不支持 | O(n²) 或 O((n+m)log n) | 贪心，每次选最近的未访问点 |
| Bellman-Ford | 单源、可有负权 | 支持 | O(nm) | 对所有边松弛 n-1 轮 |
| Floyd | 多源（任意两点） | 支持（无负环） | O(n³) | 动态规划，枚举中间点 |
Dijkstra 不能用负权边的原因，是它基于"已确定的点不会再有更短路径"这个贪心假设，负权边会破坏这个假设。Bellman-Ford 能检测负环：如果在第 n 轮还能松弛，说明存在负环。Floyd 的三重循环里，中间点 k 必须放在最外层，这个顺序不能换，因为它的本质是"只允许经过前 k 个点作为中间点"的 DP。
手写 Dijkstra 的朴素版时，核心是维护一个dist数组和visited数组，每轮找未访问的最小dist点，用它去松弛邻居，复杂度 O(n²)。如果图稀疏，用优先队列优化到 O((n+m) log n)。
6.2 最小生成树：Prim 和 Kruskal 的分工
Prim 算法像 Dijkstra，从一个点出发，每次把距离已生成树最近的点加入，适合稠密图，复杂度 O(n²)。Kruskal 则是按边权从小到大排序，用并查集判断两个端点是否已经连通，不连通就加入，适合稀疏图，复杂度 O(m log m)。
这两棵生成树的题经常考"为什么 Kruskal 要用并查集"和"为什么 Prim 适合稠密图"。前者因为要频繁判断连通性，并查集的近 O(1) 操作是关键；后者因为 Prim 是点驱动的，稠密图里点的操作次数固定为 n²，边多也不怕。
6.3 拓扑排序与关键路径，AOE 网必考
拓扑排序针对有向无环图（DAG），做法是维护入度数组，每次取入度为 0 的点，删掉它的出边并更新邻居入度。如果最后输出的点数少于总点数，说明有环。这个"判断有无环"的应用经常考。
关键路径是基于 AOE 网（边表示活动的网络）的，要算每个事件的最早发生时间和最晚发生时间，两者相等的就是关键活动，串起来就是关键路径。计算过程分四步：正向求最早时间、逆向求最晚时间、算活动的最早/最晚开始时间、找差值为 0 的活动。这套流程背熟之后，考试就是套公式。
7. 回溯、分支限界与剪枝：暴力搜索的优雅版本
回溯和分支限界本质上都是有技巧的暴力枚举，区别在于回溯用深度优先、分支限界用广度优先或优先队列。考试主要考回溯，问题一般出现在 N 皇后、子集和、装载、着色这类组合优化题上。
7.1 回溯框架：三要素一模板
回溯有三个要素：路径（已经做的选择）、选择列表（当前能做的选择）、结束条件（到达决策树底层）。模板几乎是固定的：
void backtrack(路径, 选择列表) { if (满足结束条件) { 记录结果; return; } for (选择 : 选择列表) { 做选择; backtrack(路径, 选择列表); 撤销选择; } }"做选择"和"撤销选择"成对出现，这是回溯的灵魂。理解了这一点，写回溯就像套公式。
7.2 N 皇后：剪枝怎么剪才到位
N 皇后的约束是同列、同对角线不能有两个皇后。列冲突用一个col数组判断，两条对角线分别用主对角线 = row - col + n和副对角线 = row + col判断。这三个数组就是剪枝的关键——它们让每层递归在选择时就能快速排除冲突位置，而不是生成完整排列后再验证。
复杂度上，N 皇后的搜索空间是 n!，但剪枝后实际访问的节点数远小于这个。考试如果问"剪枝的效果"，你可以说剪枝是在搜索树的内部节点提前判断并剪掉不可能产生解的分支，从而减少无效搜索。
7.3 分支限界与剪枝的取舍
分支限界法适合求解最优化问题，它用一个"界限函数"估计当前节点可能达到的最优值，如果估出来的界比当前已有的最优解还差，就剪掉这个节点。比如 0-1 背包的分支限界，用"剩余物品全按单位价值贪心装"来估计上界，一旦上界不超过当前最优，就剪枝。
考试里分支限界一般只考思路和界限函数的构造，很少要求完整手写。理解"上界估计 + 剪枝"这个核心就够了。
8. 字符串与 KMP：next 数组一次搞懂
8.1 next 数组到底在记什么
KMP 的精髓是 next 数组，它记录的是"当模式串第 j 位失配时，应该回退到哪个位置继续匹配"。next 数组的物理含义是：模式串的前缀和后缀相等的最大长度。比如模式串abab，next[4]对应abab的最长相同前后缀长度，是 2（ab）。
手算的时候，从前往后推：a没有真前后缀，next 值为 0；ab没有，0；aba是 1（a）；abab是 2。写代码时用"自己匹配自己"的方式求：
vector<int> buildNext(string p) { int m = p.size(); vector<int> nxt(m, 0); int j = 0; for (int i = 1; i < m; i++) { while (j > 0 && p[i] != p[j]) j = nxt[j - 1]; if (p[i] == p[j]) j++; nxt[i] = j; } return nxt; }这个版本求出的nxt[i]表示"以 i 结尾的子串的最长相同前后缀长度"，匹配时用j = nxt[j-1]回退。不同教材的 next 数组定义略有差别（有的从 -1 开始），考试时要看清题目的定义，这点特别重要。你们学校用哪种，你对照课本确认一遍。
8.2 KMP 匹配过程与复杂度的直观解释
匹配时，主串指针 i 从不回退，只有模式串指针 j 在失配时回退到nxt[j-1]。因为 i 只增不减，整个过程 O(n)，加上构建 next 的 O(m)，总复杂度 O(n+m)。这个"主串指针不回退"就是 KMP 相对朴素匹配 O(nm) 的优势所在，考试问你"KMP 为什么快"，答这一点就能得分。
9. 答题技巧与考场实战策略
复习到位了，考场上还得会拿分。这一节讲的是"非知识性"的技巧，但往往比知识点还值钱。
9.1 手写代码题怎么保证不丢分
手写代码题评分一般是"按点给分"，所以你要主动把得分点露出来。我的经验是：先写函数签名和注释说明参数含义，再写核心逻辑，最后补边界条件。不要一上来就写代码，先花半分钟在草稿上理清思路。
具体的几个要点：变量名写清楚，i、j这种通用没问题，但别用a、b这种无意义的名字；循环边界要明确，尤其是<和<=的取舍；递归写清楚终止条件；如果时间不够，把思路用注释写出来，往往也能拿一半分。
9.2 证明题怎么写才有分
证明题的评分看的是逻辑链条完整性，不是结论对不对。写之前先把要证的命题和已知条件列出来，然后一步一步走。交换论证的固定句式是：先假设最优解和贪心解在某一步不同，再构造交换，最后说明交换后目标函数不变差。写的时候用"假设……构造……因为……所以……"这种连接词，让阅卷老师一眼看到你的逻辑。
提示：如果实在证不出来，把相关定义和已知结论写上去，有时能拿步骤分。别空着。
9.3 时间分配：别在一道题上耗死
以 120 分钟、总分 100 分、10 道题为例，平均每题 12 分钟，但题目难度不均。我的建议是先花 2 分钟扫一遍全卷，把会做的标记出来，先做有把握的。选择填空争取在 20 分钟内完成，代码题每道控制在 15 分钟以内，留 15 分钟检查。
遇到卡壳超过 5 分钟的题，先跳过，等做完其他题再回来。考场心态很关键，一道题做不出来不代表别的题也做不出来。
10. 常见问题与排查：复习路上的坑一次说清
复习到后期，问题往往集中在几个地方。我把最常见的问题整理成速查表：
| 问题现象 | 可能原因 | 解决办法 |
|---|---|---|
| 复杂度算不对 | 主定理空隙情况没判断 | 改用递归树，或检查 f(n) 与 n^(log_b a) 是否同阶 |
| DP 状态写不出来 | 状态维度不够 | 问自己"子问题答案能否唯一推出当前答案"，不够就加维 |
| 贪心写成错的 | 排序依据选错 | 用交换论证验证，找反例测试 |
| 快排死循环 | 边界条件写漏 | 检查while里的l < r |
| KMP 和课本对不上 | next 定义不一致 | 对照课本确认 next 起点是 0 还是 -1 |
| 图论算法混淆 | 适用场景没分清 | 记对比表，重点记负权和单源/多源 |
| 回溯超时 | 剪枝不到位 | 增加可行性剪枝，提前排除冲突 |
| 手写代码总出错 | 逻辑没理清就写 | 先在草稿写思路，再落笔代码 |
这张表里的每一条，都是我在实际复习和考试里踩过的。比如快排那个死循环，当年考场上我盯着代码看了三分钟才发现是边界条件的问题，出考场一查才知道有多简单。再比如 next 数组，不同教材定义不同，我第一遍看课本、第二遍看别人的博客，两套定义混在一起，结果两道题全错。
还有个特别容易忽略的点：复习题里的"简单题"往往是陷阱。比如"写出冒泡排序的代码"看着简单，但如果老师要求你顺便分析最好情况复杂度，很多人会忘记最好情况是 O(n)（当数组已经有序且加了提前退出标志时）。复习的时候，简单题也要想一遍"老师可能怎么加料"。
实操心得：复习后期，把每类算法的"考点清单"写在一张纸上——模板、复杂度、适用场景、易错点、可能加料的地方，就这五栏。考试前一天只看这张纸，比翻课本高效十倍。
我个人在实际复习和带人复习的过程里最大的体会是：算法这门课不是靠背书能过的，它靠的是"把每一类问题的思考方式变成肌肉记忆"。你看到最大子段和能条件反射地想到分治和 DP 两种解法，看到单源最短路能立刻区分有没有负权，看到最优化问题能先判断是 DP 还是贪心——到了这个程度，考试就是走流程。至于那些手写代码的模板，别指望考前突击，从复习第一天开始，每天默写两三个，到考试那天闭着眼都能写出来。最后再分享一个小方法：把你觉得最难的那道题，用最笨的方式讲给室友听，讲得他听懂了，你就是真懂了。