算法是一个程序员的内功。算法内功是否扎实，视作专业程序员和业余程序员的分水岭。
判断一个算法是否优秀的标准。
当规模达到 N, 解法复杂度（执行步骤次数或空间占用大小）和规模的关系：
比如当 N = 100：
可见后两个复杂度基本算作无效的算法，因为计算机算不出来（除非规模很小的时候）。
N 和执行次数相关的叫时间复杂度（一般看重这个），和空间占用相关的叫空间复杂度。
递归函数的特点：
递归函数构成部分：
如果严格按照以上顺序编写，那么就属于尾递归，即这层状态和下一层无关（即所有状态都通过参数传递到下一层），优化的时候可以丢弃当前层的调用栈帧。也可以较为简单的转化为递推模型，只要建立对应参数的变量即可。
但是很多时候，第三步和第二步是相互混合的。
递推和递归思想上非常接近，都是去归纳重复子问题。不同点：递归是函数方法，递推是循环方法。
递推：
如果问题的前驱难以确定其值，如在树中找到某个值，它的父亲节点究竟是谁，难以确定。这种问题就不宜使用递推解决。
它的父节点有多个可能，递归判断其中一个不是，就能很方便的回溯到另一条路径。所以这种问题比较适合用递归来解决。
// 斐波那契数列：0,1,1,2,3,5,8,13,21...
// 递归
// 实践中需要用 Map 保存子项的结果值，避免重复计算。
function fib(n){
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}
// 递推
// n = n-1 + n-2
function fibRecursion(n){
if (n == 0) return 0;
if (n == 1) return 1;
let n1 = 1; // n-1
let n2 = 0; // n-2
for (let i = 2; i < n; ++i){
[n1, n2] = [n1 + n2, n1]; //更新 i 位置的正确值
}
return n1 + n2;
}
// 逆递推
// 实际等于手动维护调用栈，不如递归清晰
function fibReverseRecursion(n){
if (n == 0) return 0;
if (n == 1) return 1;
let st = [];
for (let i = n ; i > 1; --i){
st.push(i); // 保存当前 n 的状态
}
st.push(1);
st.push(0);
while(1){
let n2 = st.pop();
let n1 = st.pop();
let n = st.pop();//使用当前 n 的状态
n = n1 + n2; // 这里 n 的状态完全没有价值，但很多时候是有用的
st.push(n, n1);
if (st.length == 2){
st.pop();
return st.pop();
}
}
}
这套模板代码包含四部分：
特点：
// 逆递归
function fibReverse(n){
// level 当前层
// max 最大层
// ...param 其余参数，这里保存:
// 1. param[0] = 上一层结果
// 2. param[1] = 上两层结果
let f = (level, max, ...param)=>{
if (level > max){
// 1.退出条件（最终结果）
return param[0];
}
// 2.业务逻辑
let n1 = param[0] + param[1];
let n2 = param[0];
// 3.进入下一层
return f(level + 1, max, n1, n2);
// 4.清理状态(这里没有)
}
if (n == 0) return 0;
if (n == 1) return 1;
return f(2, n, 1, 0);
}
记忆化搜索状态树。递归之所以效率比较低，在于相同子状态的重复计算。如果能够把某个子状态的解保存起来，下一次直接使用，那么递归的效率将大大提高。
// 用一个缓存保存子状态的解
function fibmemo(n, memo){
if (n <= 1)
return n;
if (memo.get(n-1) === undefined)
memo.set(n-1, fibmemo(n - 1, memo));
if (memo.get(n-2) === undefined)
memo.set(n-2, fibmemo(n - 2, memo));
return memo.get(n-1) + memo.get(n-2);
}
// 在我的电脑上
// 普通 fib 递归需要 11 秒
// 经过优化后，只需要 0.017 秒
// 速度提升了 600 倍
fibmemo(45, new Map());
将问题分成若干子问题，分别求解，然后合并所有解得到最终结果。和普通的递归模板没太大分别，它只是强调分割子问题，然后合并结果这两个明确的步骤。
回溯法，就是在最后一步重置状态恢复到上一层。
function fibDivide(n){
let f = (problem, ...param)=>{
// 1. 退出条件
if (problem == 0) return 0;
if (problem == 1) return 1;
// 2. 生成子问题
let data = (pb)=>{return [pb-1, pb-2]}(problem); // 分割成两个子问题
let subproblems = (pb, data)=>{return data}(problem, data);
// 3. 处理子问题
let sub1 = f(subproblems[0]); // n - 1
let sub2 = f(subproblems[1]); // n - 2
// 4. 合并结果
return (...subs)=>{return subs[0] + subs[1]}(sub1,sub2);
// 5. 清理状态（这里没有）回溯法就在这里返回上一级状态
}
return f(n);
}
// 前序模板
function preorder(root){
if (root){
console.log(root.val);
preorder(root.left);
preorder(root.right);
}
}
// 中序模板
function inorder(root){
if (root){
inorder(root.left);
console.log(root.val);
inorder(root.right);
}
}
// 后序模板
function postorder(root){
if (root){
postorder(root.left);
postorder(root.right);
console.log(root.val);
}
}
// 深度优先（实际前三种即是深度优先）
function dfs(node, visited){
if (node && ! visited.includes(node)){
visited.push(node);
console.log(node.val);
for (let next of node.children()){
if (! visited.includes(next))
dfs(next, visited);
}
}
}
// 广度优先
function bfs(root, visited){
let queue = [];
queue.push(root);
while (queque.length != 0){
let node = queue[0];
queue.shift();
if (node && ! visited.includes(node)){
visited.add(node);
console.log(node.val);
let nodes = node.children();
queue.push(...nodes);
}
}
}
有序的二叉树，叫二叉搜索树，它保证左子树小于根，右子树大于根，即中序遍历是有序的。
二叉搜索树的查询复杂度等于树的深度，但是二叉搜索树很容易退化到链表状态，从而导致性能低下。要解决这个问题，就是使用平衡二叉树。平衡二叉树尽量让左子树和右子树的深度一致（在插入和删除的时候）。
平衡二叉树的种类：
AVL (Adelson-Velsky and Landis Tree)：
Red-black tree (红黑树)：
近似平衡二叉树，保证高度差小于两倍。
// 二分查找模板代码
function binarySearch(target, array, left, right){
if (left <= right){ // 上界和下界
let mid = Math.floor((left + right) / 2); // 有序，取中间下标
if (array[mid] == target) return mid; // 找到目标
if (target < array[mid]) // 去除下半部分
return binarySearch(target, array, left, mid - 1);
if (target > array[mid]) // 去除上半部分
return binarySearch(target, array, mid + 1, right);
}
return -1;// 没找到
}
let index = binarySearch(4, [1,2,3,4,5], 0, 4);
动态规划（即动态递推）是解决具备最优子结构的课题。所谓最优子结构是指状态树空间中存在最优的子树，而相对的其他状态可以抛弃。
以 fib 状态树为例，n 分为 n-1 和 n-2 的两个子树，但 n-2 实际上是 n-1 作为根的左子树。因此实际可以抛弃 n-2 这个子树。
观察：
2 的状态树是 1,0
3 的状态树是 1+0, 1
4 的状态树是 1+1, 1
5 的状态树是 2+1，2
即，左子树会交换到右子树，新的左子树是计算结果。可见我们并不需要重复的计算右子树。
动态规划使用递推，由底向上迭代。以 fib 为例：
// 递推公式：a(n) = a(n-1) + a(n-2)
// 自底向上
function dp(n){
let fib = (level, n, n1, n2)=>{
if (level == n){ // 1. 退出条件
return n1 + n2;
}
return fib(level + 1, n, n1 + n2, n1); // 进入上一层
}
if (n < 2) return n;
return fib(2, n, 1, 0);
}
// 动态规划模板
function dp2(n){
if (n < 2) return n; // 底层平凡解
// 1. 中间状态
let n1 = 1;
let n2 = 0;
for (let i = 2; i < n; ++i){ // 自底向上
[n1, n2] = [n1 + n2, n1]; // 2. 递推公式(更新状态)
}
return n1 + n2; // n 的解
}
一般而言，具有递推公式的中间状态，可以为队列 an，虽然不够精巧，但是它都能满足递推公式需要。因为递推公式，都是关于 an 项之间的关系。
function fibRecursion(n){
let an = [0,1];
for (let i = 2; i <= n; ++i){
an.push(an[i-1] + an[i-2]);
}
return an[n];
}
知识点：
// 单向 bfs
function bfs(root, visited){
let queue = [];
queue.push(root);
while (queque.length != 0){
let node = queue[0];
queue.shift();
if (node && ! visited.includes(node)){
visited.add(node);
console.log(node.val); // 业务逻辑
let nodes = node.children();
queue.push(...nodes);
}
}
}
// 双向 bfs
function dbfs(root1, root2, visited){
let queue1 = [root1];
let queue2 = [root2];
let next = (queue){ // 进去下一层
for (let i = queue.length; i > 0; --i){
let node = queue.shift();
if (visited.includes(node))
return;
visited.add(node);
queue.push(...node.children());
}
};
while (queue1.length != 0 || queue2.length != 0){
// 选择更小规模的来扩散，因而比单向 bfs 搜索更高效
if (queue1.length > queue2.length)
[queue1, queue2] = [queue2, queue1];
next(queue1);
if (somethings(queue1, queue2)){ // 业务逻辑
return true;
}
}
}
启发式搜索 A*，使用优先队列的 bfs，而优先队列的核心是估价函数 h(n)。它返回一个大于 0 的实数，数值越大表明优先级越高（也可以反过来，只要排序顺序的方向改变一下，就是等价的）。
因此，在每一步根据它选择路径：
优先队列有多种底层实现。一般是堆 heap。
| 数据结构 | prepend | append | lookup | insert | delete |
|---|---|---|---|---|---|
| array（数组） | O(1) | O(1) | O(1) | O(n) | O(n) |
| linkedlist（链表） | O(1) | O(1) | O(n) | O(1) | O(1) |
| skiplist（跳表） | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |
| 数据结构 | prepend | append | lookup | insert | delete |
|---|---|---|---|---|---|
| stack（栈） | O(1) | O(n) | O(n) | O(1) | O(1) |
| queue（队列） | O(n) | O(1) | O(n) | O(1) | O(1) |
| deque（双端队列） | O(1) | O(1) | O(n) | O(1) | O(1) |
| priority queue（优先队列） | O(1) | O(1) | O(log(n)) | O(1) | O(1) |
| 数据结构 | prepend | append | lookup | insert | delete |
|---|---|---|---|---|---|
| hash table（哈希） | O(1) | O(1) | O(1) | O(1) | O(1) |
| set（集合） | O(1) | O(1) | O(1) | O(1) | O(1) |
| map（字典） | O(1) | O(1) | O(1) | O(1) | O(1) |
| 数据结构 | prepend | append | lookup | insert | delete |
|---|---|---|---|---|---|
| binary tree（二叉树） | |||||
| Binary search tree（二叉搜索树） | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |
| trie tree(字典树) | |||||
| UnionFind（并查集） |