1.1 算法本质
- 种种数据结构，皆为数组（顺序存储）和链表（链式存储）的变换。
- 数据结构的关键点在于遍历和访问，即增删查改等基本操作。
- 种种算法，皆为穷举。
- 穷举的关键点在于无遗漏和无冗余。熟练掌握算法框架，可以做到无遗漏；充分利用信息，可以做到无冗余。
如何遍历 + 访问？
- 从最高层来看，各种数据结构的遍历 + 访问无非两种形式：线性的和非线性的。
- 线性就是 for/while 迭代为代表，非线性就是递归为代表。
算法的本质是【穷举】，穷举的关键：无遗漏、无冗余
- 遗漏，会直接导致答案出错，比如让求最小值，穷举时恰好把那个最小值漏掉了，这不就错了嘛。
- 冗余，会拖慢算法的运行速度，比如代码把完全相同的计算流程重复了十遍，那算法不久慢了十倍吗，可能会超过判题平台的时间限制。
为什么会遗漏？因为对算法框架掌握的不到位，不知道正确的穷举代码。
为什么会冗余？因为没有充分利用信息。
所以，当看到一道算法题，可以从这两个维度去思考：
- 1. 如何穷举？即无遗漏的穷举所有可能解。
- 2. 如何聪明地穷举？即避免穷举过程中的冗余计算，消耗尽可能少的资源求出答案。
1.2 如何穷举
什么算法的难点在「如何穷举」呢？一般是递归类问题，比方说回溯算法、动态规划系列算法。
动态规划比回溯算法更难一点。它俩本质上都是穷举，但思考模式不同，回溯算法是「遍历」的思维，而动态规划是「分解问题」的思维。
🍰
啥叫分解问题的思维？
就比方说，你看那棵树，回答我，树上有多少片叶子？
你如何穷举？顺着树枝去一片片数么？当然也可以的，但这是遍历的思维模式，胜似你手动推导排列组合的过程，属于回溯算法的范畴
如果你具备分解问题的思维模式，你应该告诉我：树上只有一片叶子，和剩下的叶子。
还有不开窍的小同学追问，那剩下的叶子有多少呢？答曰，只有一片，和剩下的叶子。不要再往下问了，只能说，谜底就在谜面上，到了那个时候，你自然知道剩多少了。
1.3 如何聪明地穷举
什么算法的难点在「如何聪明地穷举」呢？一些耳熟能详的非递归算法技巧，都可以归在这一类。
- 最简单的例子，比方说让你在有序数组中寻找一个元素，用一个 for 循环暴力穷举谁都会，但 二分搜索算法 就是更聪明的穷举方式，拥有更好的时间复杂度。
- 还有 Union Find 并查集算法 告诉你一种高效计算连通分量的技巧，理论上说，想判断图中的两个节点是否连通，我用 DFS/BFS 暴力搜索（穷举）肯定可以做到，但人家 Union Find 算法硬是用数组模拟树结构，给你把连通性相关的操作复杂度给干到 O（1） 了。
- 再比如贪心算法技巧，所谓贪心算法就是在题目中发现一些规律（专业点叫贪心选择性质），使得你不用完整穷举所有解就可以得出答案。当然，并不是所有问题都存在贪心选择性质让你投机取巧，所以全量穷举虽然朴实无华且枯燥，但真的是任何情况下都可以用的。
这就属于聪明地穷举，大佬们把这些技巧发明出来，学过就会用，没学过恐怕很难想出这种思路。
1.4 数组/单链表系列算法
- 单链表常考的技巧就是双指针，属于「如何聪明地穷举」这一类。
- 数组常用的技巧有也是双指针相关的技巧，也都属于「如何聪明地穷举」这一类。
具体表现形式：
- 1. 二分搜索技巧，可以归为两端向中心的双指针。如果让在数组中搜索元素，一个 for 循环花 O（N）时间穷举肯定能搞定，但是二分搜索告诉你，如果数组是有序的，它只要 O（logN） 的复杂度，这不就是一种更聪明的搜索方式么。
- 2. 滑动窗口算法技巧，典型的快慢双指针。用嵌套 for 循环花 O（N2） 的时间肯定可以穷举出所有子数组，也就必然可以找到符合题目要求的子数组。但是滑动窗口算法表示，在某些场景下，它可以用一快一慢两个指针，只需 O（N）的时间就可以找到答案，这就是更聪明地穷举方式。
- 3. 前缀和技巧，如果频繁地让计算子数组的和，每次用 for 循环遍历肯定没问题，但前缀和技巧预计算一个preSum数组，就可以避免循环。（空间换时间思想）
- 4. 差分数组技巧，如果频繁地让对子数组进行增减操作，也可以每次用 for 循环去操作，但差分数组技巧维护一个 diff 数组，也可以避免循环。
1.5 二叉树系列算法
二叉树系列属于「如何穷举」一类。
二叉树题目的递归解法可以分两类思路：
- 第一类是遍历一遍二叉树得出答案，对应着 回溯算法核心框架。
- 第二类是通过分解问题计算出答案，对应着 动态规划核心框架。
遍历思维模式
就比如说计算二叉树最大深度这个问题让你实现 maxDepth 这个函数：
class Solution {
// 记录最大深度
int res = 0;
// 记录当前遍历节点的深度
int depth = 0;
// 主函数
int maxDepth(TreeNode root) {
traverse(root);
return res;
}
// 二叉树遍历框架
void traverse(TreeNode root) {
if (root == null) {
// 到达叶子节点
res = Math.max(res, depth);
return;
}
// 前序遍历位置
depth++;
traverse(root.left);
traverse(root.right);
// 后序遍历位置
depth--;
}
}这个逻辑就是用 traverse 函数遍历了一遍二叉树的所有节点，维护 depth 变量，在叶子节点的时候更新最大深度。
回溯算法本质就是遍历多叉树，只要能把问题抽象成树结构，就一定能用回溯算法解决。
分解问题的思维模式
同样是计算二叉树最大深度这个问题，也可以写出下面这样的解法：
// 定义：输入根节点，返回这棵二叉树的最大深度
int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
// 递归计算左右子树的最大深度
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
// 整棵树的最大深度就是左右子树的最大深度加一
int res = Math.max(leftMax, rightMax) + 1;
return res;
}思路扩展
二叉树的前序遍历亦可用「分解问题」的思路，注意前序遍历的结果，根节点的值在第一位，后面接着左子树的前序遍历结果，最后接着右子树的前序遍历结果。
// 定义：输入一棵二叉树的根节点，返回这棵树的前序遍历结果
List<Integer> preorder(TreeNode root) {
List<Integer> res = new LinkedList<>();
if (root == null) {
return res;
}
// 前序遍历的结果，root.val 在第一个
res.add(root.val);
// 后面接着左子树的前序遍历结果
res.addAll(preorder(root.left));
// 最后接着右子树的前序遍历结果
res.addAll(preorder(root.right));
return res;
}这就是用分解问题的思维模式写二叉树的前序遍历，如果写中序和后序遍历也是类似的。
层次遍历
除了动归、回溯（DFS）、分治，还有一个常用算法就是 BFS 了，BFS 算法核心框架 就是根据下面这段二叉树的层序遍历代码改装出来的：
// 输入一棵二叉树的根节点，层序遍历这棵二叉树
void levelTraverse(TreeNode root) {
if (root == null) return;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int depth = 1;
// 从上到下遍历二叉树的每一层
while (!q.isEmpty()) {
int sz = q.size();
// 从左到右遍历每一层的每个节点
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
// 将下一层节点放入队列
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
depth++;
}
}更进一步，图论相关的算法也是二叉树算法的延续。
比如 图论基础，环判断和拓扑排序 和 二分图判定算法 就用到了 DFS 算法；再比如 Dijkstra 算法模板，就是改良版的 BFS 算法。