Appearance
23 算法模板：如何让高频算法考点秒变默写题？
今天开始进行算法模板的复习和整理。授人以鱼，不如授人以渔。在本讲，我的目的是教会你如何做知识的整理和模板的整理，而不是直接给你一些现成的东西，让你去死记硬背。无论是思维导图，还是代码模板，你自己整理一遍的收获会更大。
今天我们主要介绍两种方法：
通过思维导图将学过的知识添加到你的知识树中；
将刷过的题目整理成代码模板，放到你的代码模板库中。
排序
我们在学习排序的时候，主要讨论了合并模板和快速排序两种排序，现在就可以利用下面这个思维导图进行快速复习。
合并的技巧
对于合并排序来说，我觉得最重要的是掌握下面这段合并的小技巧：
java
int i = b;
int j = m;
int to = b;
// 将两个子数组进行合并, 注意下面是一个很重要的模板
// 这里的判断条，是只要两个子数组中还有元素
while (i < m || j < e) {
// 如果右子数组没有元素 或 左子数组开头的元素小于右子数组开头的元素
// 那么取走左子数组开头的元素
// 考点：a[i] <= a[j]这样可以保证合并排序是稳定的，不要写错!
if (j >= e || i < m && a[i] <= a[j]) {
t[to++] = a[i++];
} else {
// 否则就是取右子数组开头的元素
t[to++] = a[j++];
}
}可以看到 while 语句中 if 语句的写法（上述代码第 11 行）用了最简洁的代码处理了各种边界条件！
三路切分
在《08 | 排序：如何利用合并与快排的小技巧，解决算法难题？》介绍快速排序时，三路切分也是一个高频出现的知识点，所以我们需要掌握这个代码模板，如下所示：
java
// 辅助函数：交换数组中的两个元素
void swap(int[] A, int i, int j) {
int t = A[i];
A[i] = A[j];
A[j] = t;
}
// 三路切分
int threeSplit(int[] A, int b, int e) {
if (b >= e) {
return 0;
}
// 我们取数组中间的数
final int m = b + ((e - b) >> 1);
final int x = A[m];
// 注意我们的初始区间有四个：
// [b, l) [l, i) [i, r] (r, N)
// [小于) [等于) [未知] (大于)
int l = b;
int i = b;
int r = e - 1;
while (i <= r) {
if (A[i] < x) {
swap(A, l++, i++);
} else if (A[i] == x) {
i++;
} else {
swap(A, r--, i);
}
}
// 切分完毕之后，只有三个区间
// [b, l) [l, i) [i, N)
// 首先看中间的区间
if (i - l == 1)
return A[l];
// 再看左区间
if (((l - b) & 0x01) == 1) {
return threeSplit(A, b, l);
}
// 再看右区间
return threeSplit(A, i, e);
}二分
我们将二分的知识点整理如下：
当已知一个题目可以用二分进行破解时，就可以使用 lowerBound 和 upperBound 这两个标准的二分的模板了。
此外，我们还需要记住这两个模板的使用的条件：
lowerBound 用于查找有序数组中最左边出现的元素（闭）。
upperBound 用于查找有序数组中最右边出现的元素（开）。
注意，我们在条件部分加了"开闭"两个字！其含义如下：
当给定数组 A[] = {1,2,2,2,3}，运行 lowerBound(A, 2) 返回下标 1，而运行 upperBound(A,2) 却返回下标 4，但此时 A[4] = 3。
因此，我们还需要注意，lowerBound 与 upperBound 返回值组成的区间是一个左闭右开的区间，如下所示：
java
[lowerBound(A,2), upperBound(A,2)) = [1, 4)一定要记住这里的左闭右开原则！
lowerBound
其中 lowerBound 的代码模板如下：
java
int lowerBound(long[] A, int n, long target) {
int l = 0, r = n;
while (l < r) {
final int m = l + ((r - l) >> 1);
if (A[m] < target) {
l = m + 1;
} else {
r = m;
}
}
return l;
}upperBound
upperBound 的模板代码如下：
java
int upperBound(long[] A, int n, long target) {
int l = 0, r = n;
while (l < r) {
final int m = l + ((r - l) >> 1);
if (A[m] <= target) {
l = m + 1;
} else {
r = m;
}
}
return l;
}其实我们只需要记忆 lowerBound 模板就够了，因为两个模板之间的差异只有一处：
lowerBound：A[m] < target
upperBound：A[m] <= target
这里和你分享一个我的记忆方法。当 A[m] <= target 的时候，标志着 m 还可以往右移动一段距离，因为 upperBound 找到的一般都在更右边的位置，因此带有"A[m] <= target"的是 upperBound。
双指针
双指针的知识我们总结如下：
需要熟练掌握的代码模板，一共有 3 个。
最长区间
求最长区间的代码模板长成这样：
java
int maxLength(int[] A) {
int N = A.length;
// 区间的左指针
int left = -1;
int ans = 0;
for (int i = 0; i < N; i++) {
// assert 在加入A[i]之前，(left, i-1]是一个合法有效的区间
// step 1. 直接将A[i]加到区间中，形成(left, i]
// step 2. 将A[i]加入之后，惰性原则
while (check((left, i]))/*TODO 检查区间状态是否满足条件*/) {
++left; // 如果不满足条件，移动左指针
// TODO 修改区间的状态
}
// assert 此时(left, i]必然满足条件
ans = max(ans, i - left);
}
return ans; // 返回最优解
}注意：在解题的时候，需要根据具体的题目条件，在模板的基础上写一点状态更新的代码，也就是要替换掉代码模板中的"TODO"部分。
定长区间
其实定长区间就是固定窗口大小的滑动窗口算法，这里我整理好了一个通用的模板，如下所示：
java
int fixedLength(int[] A, int windowSize) {
final int N = A == null ? 0 : A.length;
int left = -1;
for (int i = 0; i < N; i++) {
// step 1. 直接将A[i]加到区间中，形成(left, i]
// TODO 修改区间的状态
// 如果滑动窗口还太小
if (i - left < windowSize) {
continue;
}
// assert 此时(left, i]长度必然等于windowSize
// TODO 判断区间的状态是否满足约束条件
left++;
// step 2. 移除A[left]
// TODO 修改区间状态
}
return ans; // 返回最优解注意：这个代码模板也是需要根据具体的题目条件完成"TODO"的部分。不同的题目，状态更新的代码可能会稍有不同。
最短区间
最短区间的代码模板如下：
java
int minimalRange(int[] A) {
final int N = A == null ? 0 : A.length;
// 子串的左边，采用左开右闭原则(left, i]表示一个子串
int left = -1;
// 记录最短的子串的长度
int ans = A.length + 1;
for (int i = 0; i < N; i++) {
// 注意 在加入A[i]之前，(left, i-1]可能不满足条件!
// step 1. 直接将A[i]加到区间中，形成(left, i]
// step 2. TODO 更新区间的状态
while (区间超出/满足条件) {
ans = Math.min(ans, i - left);
// step 3. 移除A[++left];
// step 4. TODO 更新区间的状态
}
// assert ! 区间(left, i]到这里肯定不满足条件
}
return ans;
}注意：状态更新的代码同样需要根据题目的条件完成"TODO"的部分。
贪心
虽然说贪心算法是一种思想，不过还是有一些代码模板需要你掌握。比如区间不重复的最大数目模板，如下所示：
java
int nonOverlapIntervals(int[][] A) {
final int N = A == null ? 0 : A.length;
// 将区间进行排序
Arrays.sort(A, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[1] == b[1] ? 0 : (a[1] < b[1] ? -1 : 1);
}
});
// 已重叠的区间的最右端点
int maxEnd = Integer.MIN_VALUE;
// 不重叠 的区间的个数
int ans = 0;
// 开始贪心算法
for (int i = 0; i < N; i++) {
final int start = A[i][0];
if (maxEnd <= start) {
maxEnd = A[i][1];
ans++;
}
}
return ans;
}此外，在《11 | 贪心：这种思想，没有模板，如何才能掌握它？》中我们介绍过"青蛙跳"问题， 实际上该解法还可以解决一系列题目，比如"第 11 讲"的练习题 5，练习题 6 等。因此，我把这个算法模板叫作青蛙跳模板。
java
boolean canJump(int[] A) {
final int N = A == null ? 0 : A.length;
// 一开始，在正式开始第一次扫描之前，肯定什么元素都还没有扫描过
// 所以之记录之前扫描位置设置为-1
int preScanedPos = -1;
// 根据题意
// 当前能覆盖到数组的第0个元素。也就是当前可以够得着的元素
int curCoveredRange = 0;
// 如果当前
while (curCoveredRange < N - 1) {
int oldCoveredRange = curCoveredRange;
// 根据优化1和优化2，我们只需要遍历
// [preScanedPos + 1, oldCoveredRange]即可。
// 然后不停更新curCoveredRange
for (int i = preScanedPos + 1; i <= oldCoveredRange; i++) {
// 1. 这个区间和我们已经覆盖的范围是相连的!
// 满足相连性
// 2. 如果这个区间能覆盖得更远
if (i + A[i] > curCoveredRange) {
// 更新我们能cover的范围
curCoveredRange = i + A[i];
}
}
// 如果发现不能更新覆盖范围，说明已经没有变长的可能性了。
if (oldCoveredRange == curCoveredRange) {
return false;
}
// 我们记住上次已经扫描过的位置
preScanedPos = oldCoveredRange;
}
return true;
}回溯
关于回溯，我经常从两个方向思考：
只看第 i 个人怎么选；
"有借有还"。
关于这两点，希望你看了下面的这个思维导图还能够想起来。
回溯的代码模板只有一个，如下所示：
java
void backtrace(int[] A,
int i, /*第i个人*/
Box s, /*箱子*/
answer/*存放所有的答案*/) {
final int N = A == null ? 0 : A.length;
if (状态满足要求) {
answer.add(s);
}
if ([i, ...., 后面）的人都没有任何选项了) {
return;
}
for 宝石 in {第i个人当前所有宝石选项} {
s.push(宝石);
backtrace(A, i + 1, s, answer);
s.pop();
}
}DFS 与 BFS
DFS 与 BFS 的知识点我压缩在了一张思维导图里：
关于代码模板，你只需要掌握两个。
DFS
通常而言，DFS 算法会用到两个模板，一个用于遍历，另一个用于收集符合条件的解。其中用于遍历的代码模板如下：
java
boolean vis[N];
void DFS(int start) {
if start == end {
success = true
return
}
// 遍历当前可以做出的选择
for opt in getOptions(start) {
if (vis[opt]) continue;
vis[opt] = true;
dfs(opt);
if success {
return;
}
}
}用于收集符合条件的解的代码模板如下：
java
void dfs(A,
int start, /* start 表示出发点*/
vis, /* 记录每个点是否已经访问 */
path, /* 路径*/
answer/*存放最优的答案*/) {
final int N = A == null ? 0 : A.length;
if (状态满足要求) { // 是更好的解吗？
if (s better_than ans) {
ans = s
}
return;
}
for next in {start点的后继点} {
if !vis[next] {
path.append(next);
vis[next] = true;
dfs(A, next, vis, path, answer);
path.pop();
vis[next] = false;
}
}
}BFS
巧合的是，BFS 也有两种写法，一种是使用队列，另一种是使用"两段击"。其中使用队列的代码写法如下：
java
bfs(s) { // s表示出发点
q = new queue()
q.push(s), visited[s] = true // 标记s为已访问
while (!q.empty()) {
u = q.pop() // 拿到当前结点
for next in getNext(u) { // 拿到u的后继next
if (!visited[next]) { // 如果next还没有访问过
q.push(next)
visited[next] = true
}
}
}
}使用"两段击"的代码写法如下：
java
bfs(s) { // s表示出发点
cur = {s};
visited[s] = true; // 标记s为已访问
while (!cur.empty()) {
next = [];
for c in cur {
for next in getNext(c) {
if (!visited[next]) { // 如果next还没有访问过
next.append(next);
visited[next] = true;
}
}
}
cur = next;
}
}动态规划
动态规划其实并没有太多的模板可以套，你需要通过实战练习不停地提高自己的应对能力。掌握动态规划的重点在于 6 步分析法，如下图所示：
这里我们重点看一下需要你熟练掌握的 KMP 算法模板（你还记得求 next 数组时的动态规划吗？），如下所示：
java
int[] buildNext(String sub) {
final int N = sub == null ? 0 : sub.length();
int[] next = new int[N + 1];
int i = 0;
int j = -1;
next[0] = -1;
while (i < N) {
if (j == -1 || sub.charAt(i) == sub.charAt(j)) {
i++;
j++;
if (i < sub.length() && j < sub.length() &&
sub.charAt(i) == sub.charAt(j)) {
next[i] = next[j];
} else {
next[i] = j;
}
} else {
j = next[j];
}
}
return next;
}
int KMP(String main, String sub) {
int i = 0;
int j = 0;
final int alen = main.length();
final int blen = sub.length();
int[] next = buildNext(sub);
while (i < alen && j < blen) {
if (-1 == j || main.charAt(i) == sub.charAt(j)) {
// 如果匹配成功，那么向前走
// 这里和暴力的方法没有区别
i++;
j++;
} else {
j = next[j];
}
}
// 看一下是不是匹配完了
return j == blen ? i - blen : -1;
}总结
整理好算法的代码模板之后，最后我再强调一点，也是新手往往容易犯错的地方。
不要试图把刷过的所有题都放到代码模板中，因为你复习的时候容易没有重点。另外，人的记忆能力是有限的，如果你强记一段代码，可能效果并不好。更重要的是勤于将知识进行整理、归纳以及压缩。然后将它们打包成知识库中的"积木"，在需要的时候直接拿来用，而不是再从 0 到 1 推导。
算法模板就整理到这里了，接下来，我将和你聊聊我的大厂面试经历，谈谈我对算法学习的看法，让我们继续前进。