代码拉取完成，页面将自动刷新
同步操作将从 deepinwiki/wiki 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
算法是一个程序员的内功。算法内功是否扎实，视作专业程序员和业余程序员的分水岭。
严格意义来说，算法包含一切解题的思路，但是一般而言，计算机算法有它自己的特点。
3*?=? ，或者 ?*? = ?。又比如数学问题会问你排列组合有多少种，但是计算机问题可能就是把所有排列组合一一罗列出来。这种问题对人类来说很繁琐，所以也不是数学的研究重点，但是计算机依赖其高速运行的特点，可以完成这类大规模，又繁琐的问题，而往往程序员需要面对的就是这类问题。全面性思维。你必须把问题想清楚，问题的解域在哪里，不能遗漏某个分支。这个是计算机算法的最基础要求。这里面涉及逻辑学的内容，比如最基本的分支结构，怎样才能定义清晰和全面，这都想不清楚，那其他都是空想。只有全面，才能保证正确，只有正确，算法才有意义。有时候想太多（深入，瞎几把乱想）不是好事，但得想全面，把解包裹起来，是基础。
计算机算法的基础是暴力求解。计算机算法是通过重复大量简单的步骤，求解复杂问题。即使是一时间找不到高效解法的问题，只要能够正确的定义解域和判定条件，也可以一个一个尝试，而求出解。这一定是正确的，只是效率低罢了。
往往有一个相对简单的判断该解是否正确的方法。从而让暴力求解得以进行。所以，这个点也许不起眼，但是往往能帮助你找到解题灵感。
剩余的是提高效率的一切方法：
一、数学公式推导。（除非你是做数学研究的）
二、数学归纳法。有效降低存储的规模，因为它只依赖前件推导后件，从而遍历整个问题空间。也就是我们不需要存储整个问题域，只需要存储前后件。
三、模型概括。很多问题虽然看上去不同，但往往都能规整成相同的模型。积累解题经验，是提高算法能力的不二选择。比如树的搜索，几乎能类比大部分现实中的问题。因为计算机很多东西喜欢组织成树的结构，比如 xml，文件夹 等等。如果不用专门的经过专家总结的树算法，面对这类问题自己乱写，可能就写的就比较复杂，也没有复用的可能。所以为什么要学习数据结构，就是希望用一般性的久经考验的算法思路去解决现实中的问题。一定要培养自己看问题，并总结模型构型的能力。人类的能力是有限的，你可能记不清楚算法的细节，但是看问题的方式，习惯，是可以保证你快速建立解题思路的。
总结：
判断一个算法是否优秀的标准。
当规模达到 N, 解法复杂度（执行步骤次数或空间占用大小）和规模的关系：
比如当 N = 100：
可见后两个复杂度基本算作无效的算法，因为计算机算不出来（除非规模很小的时候）。
N 和执行次数相关的叫时间复杂度（一般看重这个），和空间占用相关的叫空间复杂度。
本节摘录一些基本的逻辑和集合概念，更多只能自己找相关资料和做思维训练。
布尔逻辑：
a+(b*c) = (a+b)*(a+c)： 分配律a+0 = a; a*0=0; a+1=1; a*1 = a ： 有界律1*1 = 1; 1*0 = 0; 0*0 = 0 ： 与运算// 对应分支语句
if (a 且 b) => a * b
else if (c 或 d) => -(a*b)*(c+d)
else => -(a*b)*-(c+b) = -(a*b)*-c*-d
// 非（a且b）且非c且非d
// 当条件比较多的时候，要完全的罗列所有组合其实比较困难
// 只针对某些条件，而对剩余进行统一处理
// 肯定式（多分支）
switch(x){
ab=>...
c,d=>...
default error;
}
// 否定式(优先拒绝，通常只有一个主流程)
if (-a 或 -b) return;
if (-c 且 -d) return;
f(a,b)
f(c)
f(d)
...
递归函数的特点：
递归函数构成部分：
如果严格按照以上顺序编写，那么就属于尾递归，即这层状态和下一层无关（即所有状态都通过参数传递到下一层），优化的时候可以丢弃当前层的调用栈帧。也可以较为简单的转化为递
推模型，只要建立对应参数的变量即可。
但是很多时候，第三步和第二步是相互混合的。
递推和递归思想上非常接近，都是去归纳重复子问题。不同点：递归是函数方法，递推是循环方法。
递推：
// 斐波那契数列：1,1,2,3,5,8,13,21...
// 递归
// 实践中需要用 Map 保存子项的结果值，避免重复计算。
function fib(n){
if (n == 1) return 1;
if (n == 2) return 1;
return fib(n - 1) + fib(n - 2);
}
// 递推
// n = n-1 + n-2
function fibRecursion(n){
if (n == 1) return 1;
if (n == 2) return 1;
let n1 = 1; // n-1
let n2 = 1; // n-2
for (let i = 3; i < n; ++i){
[n1, n2] = [n1 + n2, n1]; //更新 i 位置的正确值
}
return n1 + n2;
}
// 逆递推
// 实际等于手动维护调用栈，不如递归清晰
function fibReverseRecursion(n){
if (n == 1) return 1;
if (n == 2) return 1;
let st = [];
for (let i = n ; i > 2; --i){
st.push(i); // 保存当前 n 的状态
}
st.push(1);
st.push(1);
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 的值，所以存在最优子结构。
而且 n-2 实际上是 n-1 作为根的左子树。因此实际可以抛弃 n-2 这个子树（的计算）。
观察：
| 序 | 左 | 右 |
|---|---|---|
| 2 | 1 | 0 |
| 3 | 1 | 1 |
| 4 | 2 | 1 |
| 5 | 3 | 2 |
即，左子树会交换到下一级的右子树，下一级新的左子树是上一级的和。可见我们并不需要重复的计算右子树，只需要套用上一级的左子树即可。
动态规划使用递推，由底向上迭代。以 fib 为例：
// 递推公式：a(l) = a(n1) + a(n2)
// 自底向上
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（并查集） |
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手