什么是算法
注意事项
- 正则表达式—效率非常低，慎用！！！
- 累计各个元素的连续长度，最后求最大值一徒增空间复杂度
- PS:算法题尽量用“低级”代码，慎用语法糖或者高级API
- 尽量不要转换数据结构，尤其数组这种有序结构
- 尽量不要用内置API，如：reverse，不好识别复杂度
- 数字操作最快，其次是字符串
- 要注意实际复杂度，不要被代码表面迷惑（如：跳步）
- 优化嵌套循环，可以考虑”双指针”
- 算法题慎用正则表达式（实际工作可以用） ```typescript const str = ‘100abc’ const reg = /^\d+/
console.time(‘reg’) for (let i = 0; i < 100 * 10000; i++) { reg.test(str) } console.timeEnd(‘reg’)
console.time(‘indexOf’) for (let i = 0; i < 100 * 10000; i++) { str.indexOf(‘100’) } console.timeEnd(‘indexOf’)
<a name="hnq8K"></a># 递推法递推是[序列](https://baike.baidu.com/item/%E5%BA%8F%E5%88%97/1302588)[计算机](https://baike.baidu.com/item/%E8%AE%A1%E7%AE%97%E6%9C%BA)中的一种常用算法。它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的[庞大](https://baike.baidu.com/item/%E5%BA%9E%E5%A4%A7/16883)的计算过程转化为[简单](https://baike.baidu.com/item/%E7%AE%80%E5%8D%95/2903)[过程](https://baike.baidu.com/item/%E8%BF%87%E7%A8%8B)的多次[重复](https://baike.baidu.com/item/%E9%87%8D%E5%A4%8D/33187)，该算法利用了计算机速度快和[不知疲倦](https://baike.baidu.com/item/%E4%B8%8D%E7%9F%A5%E7%96%B2%E5%80%A6)的机器特点。<a name="kQEYK"></a># [递归法](https://baike.baidu.com/item/%E9%80%92%E5%BD%92/1740695)<a name="lUY1z"></a># [穷举法/暴力破解法/枚举法](https://baike.baidu.com/item/%E6%9E%9A%E4%B8%BE%E6%B3%95/2473707?fromtitle=%E6%9A%B4%E5%8A%9B%E7%A0%B4%E8%A7%A3&fromid=5828444)<a name="IVmZz"></a># [分治法](https://baike.baidu.com/item/%E5%88%86%E6%B2%BB%E6%B3%95)- 分而治之是算法设计中的一种方法。- 它**将一个问题分成多个和原问题相似的小问题**，**递归**解决小问题，再将结果合并以解决原来的问题。<a name="xOkRx"></a>## 应用场景- 归并排序- 快速排序- 二分搜索- 反转二叉树<a name="dN6xM"></a>## 题目<a name="FzBJb"></a>### [猜数字大小](https://leetcode-cn.com/problems/guess-number-higher-or-lower/)- [**使用二分查找**](https://www.yuque.com/niweixiaoshihaomei/bx33ma/soxyq8#YZza9)<a name="wzLtT"></a>### [翻转二叉树](https://leetcode-cn.com/problems/invert-binary-tree/)```javascriptconst invertTree = function (root) {if (!root) {return null;}return {val: root.val, left: invertTree(root.right), right: invertTree(root.left)}};
相同的树
const isSameTree = function (p, q) {
if (!p & !q) return true;
if (p && q && p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)) {
return true;
}
return false;
}
对称二叉树
const isSymmetric = function (root) {
if (!root) return true;
const isMirror = (l, r) => {
if (!l && !r) return true;
if (l && r && l.val === r.val && isMirror(l.left, r.right) && isMirror(l.right, r.left)) {
return true;
}
return false;
}
return isMirror(root.left, root.right);
};
动态规划
- 动态规划（Dynamic Programming）是算法设计中的一种方法，和分治法相似，但又有不同。
- 它将一个问题分解为相互重叠的子问题，通过反复求解子问题，来解决原来的问题。
动态规划的口诀
- 定义子问题 + 反复执行；
- 递归+记忆化 => 递推（当你用动态规划解题时，但是第一步不知道怎么下手时，可以先尝试用递归推导）；
- 状态的定义：dp[n]
- 状态转移方程：dp[n]=best_of(dp[n-1],dp[n-2],…)，这里的 best_of 可以是 Math.min/Math.max 等
- 最优子结构
动态规划与分治法的区别
- 主要看子问题是否是相互重叠：如果是相互重叠的则为动态规划，如果是相互独立的，则为分而治之。
参考
https://www.bilibili.com/video/BV13Q4y197Wg
题目
斐波那契数列
递归
/**
* 斐波那契数列（递归）
* @param n n
*/
// 0 1 1 2 3 5 8 13 21 34 ...
// 0 1 1 2 3 5 8 13 21 34 55...
function fibonacci(n) {
// if (n <= 0) return 0
// if (n === 1) return 1
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2)
}
// console.log(fibonacci(10))
// 时间复杂度为 O(2^n)
记忆化
- 将 fibonacci(n - 1) 和 fibonacci(n - 2) 的计算结果缓存起来，这样下次就不需要重新计算
function fibonacci2(n) {
if (n <= 1) return n;
let n1 = 1 // 记录 n-1 的结果
let n2 = 0 // 记录 n-2 的结果
let res = 0
for (let i = 2; i <= n; i++) {
res = n1 + n2
// 记录中间结果
n2 = n1
n1 = res
}
return res
}
function fib(n) {
if (n <= 1) return n;
const arr = [0, 1];
for (let i = 2; i <= n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}
爬楼梯
硬推导（找数字规律）
// n = 1 => 1
// n = 2 => 2 <= [1,1] [2]
// n = 3 => 3 <= [1,1,1] [1,2] [2,1]
// n = 4 => 5 <= [1,1,1,1] [1,1,2] [1,2,1] [2,1,1] [2,2]
// n = 4 的推导过程：
// 第一次只爬1个台阶，还剩3个台阶
// [1,...]
// 第二次只爬1个台阶，还剩2个台阶
// [1,1,...]
// 第三次只爬1个台阶，还剩1个台阶
// => [1,1,1,1]
// 第三次爬2个台阶
// => [1,1,2]
// 第二次爬2个台阶 ，还剩1个台阶
// [1,2,...]
// => [1,2,1]
// 第一次爬2个台阶，还剩2个台阶
// [2,...]
// 第二次只爬1个台阶，还剩1个台阶
// => [2,1,1]
// 第二次爬2个台阶
// => [2,2]
// 所以 n = 4 时，一共有 5种 爬法
// n = 5 => 8
// n = 5 的推导过程：
// 第一次只爬1个台阶，还剩4个台阶
// [1,...]
// 第二次只爬1个台阶，还剩3个台阶
// [1,1,...]
// 第三次只爬1个台阶，还剩2个台阶
// [1,1,1,...]
// 第四次只爬1个台阶，还剩1个台阶
// => [1,1,1,1,1]
// 第四次爬2个台阶
// => [1,1,1,2]
// 第三次爬2个台阶，还剩1个台阶
// => [1,1,2,1]
// 第二次爬2个台阶，还剩2个台阶
// [1,2,...]
// 第三次只爬1个台阶，还剩1个台阶
// => [1,2,1,1]
// 第三次爬2个台阶
// => [1,2,2]
// 第一次爬2个台阶，还剩3个台阶
// [2,...]
// 第二次只爬1个台阶，还剩2个台阶
// [2,1,...]
// 第三次只爬1个台阶，还剩1个台阶
// => [2,1,1,1]
// 第三次爬2个台阶
// => [2,1,2]
// 第二次爬2个台阶，还剩1个台阶
// => [2,2,1]
// 所以 n = 5 时，一共有 8种 爬法 [1,1,1,1,1] [1,1,1,2] [1,1,2,1] [1,2,1,1] [1,2,2] [2,1,1,1] [2,1,2] [2,2,1]
// n = 6 => 13
// n = 7 => 21
// ...
f(n) = f(n - 1) + f(n - 2);
倒推法
- 当 n=1 时，只有一种爬法：f(1)=1；
- 当 n=2 时，有两种爬法：一阶一阶的爬 或者 一次就爬两阶， f(2)=2；
- 当 n=3 时，因为一次只能爬一阶或者二阶，所以在爬最后一次就到最后一阶台阶时，我们有两种爬法：
- 最后一次爬，选择爬一阶：最后一次爬之前，所在位置为 (n - 1)，即为阶梯 2
- 最后一次爬，选择爬二阶：最后一次爬之前，所在位置为 (n - 2)，即为阶梯 1
- 因为最后一次爬有两种爬法，所以只需要计算这两种爬法分别所需的爬法（也就是爬到对应阶梯位置时需要的爬法，如：n-1 / n-2 阶梯位置）就行，也就是 (n=3 时总的爬法) = 两种爬法 = （爬法一：n=1时的爬法种数） + （爬法二：n=2 时的爬法种数） = 2 + 1；
- f(n) = f(n - 1) + f(n - 2)
打家劫舍
三角形最小路径和
- 倒推法：底部的值 + 倒数第二排的值可以计算出局部最小的路径。
乘积最大子数组
最长递增子序列
零钱兑换
编辑距离
股票系列
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/dai-ma-sui-xiang-lu-188-mai-mai-gu-piao-w01v7/
https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92-%E8%82%A1%E7%A5%A8%E9%97%AE%E9%A2%98%E6%80%BB%E7%BB%93%E7%AF%87.html#%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/mai-mai-gu-piao-wen-ti-by-chen-wei-f-kavn/
买卖股票的最佳时机
买卖股票的最佳时机 II
买卖股票的最佳时机 III
买卖股票的最佳时机 IV
最佳买卖股票时机含冷冻期
买卖股票的最佳时机含手续费
状态定义：
dp[i] => 到 i 天时最大的收益值
dp[i-1] => 到 i 天的前一天的最大的收益值
(-a[1]) 表示当天买股票花去的钱
(a[1]) 表示当天卖股票花去的钱
状态转移方程：
dp[i] = dp[i-1] + (-a[i]) // 买股票
dp[i] = dp[i-1] + a[i] // 卖股票
因为无法得知 i-1 天时，是否能买或者卖股票（如果已经有股票了就不能买进，如果没有股票则可以买进），所以需要用二维数组记录当天的股票信息，
==> dp[i][j] = dp[i-1] + a[i] // [j] 的值为 0/1，表示是否拥有股票
// 情况一
// dp[i-1,0] 表示前一天不进行任何操作
// dp[i-1,1] + a[i] 表示前一天卖股票
dp[i,0] = max( dp[i-1,0] , dp[i-1,1] + a[i])
// 情况二
// dp[i-1,1] 表示前一天不进行任何操作
// dp[i-1,0] - a[i] 表示前一天买股票
dp[i,1] = max( dp[i-1,1] , dp[i-1,0] - a[i])
如果题目要求只能进行 k 次买股票，那么还得再加一维数组，用来存储当前买股票的次数
==> dp[i,j,k] 三维数组也可以变成 dp[i,k,j]
// 情况一
// dp[i-1,k,0] 表示前一天不进行任何操作
// dp[i-1,k,1] + a[i] 表示前一天卖股票
dp[i,k,0] = max( dp[i-1,k,0] , dp[i-1,k-1,1] + a[i])
// 情况二
// dp[i-1,k,1] 表示前一天不进行任何操作
// dp[i-1,k-1,0] - a[i] 表示前一天买股票
dp[i,k,1] = max( dp[i-1,k,1] , dp[i-1,k-1,0] - a[i])
// 最终求最大值时，需要基于前一天的收益值（因为当天肯定不能买股票，会使收益值降低），比较每个 k 值对应的收益值，同时 j 的值肯定为 0，因为只有卖出股票才能比较彼此的价格大小
==> max( dp[i-1,0,0], dp[i-1,1,0], dp[i-1,2,0], ... , dp[i-1,k,0] )
贪心算法
- 贪心算法是算法设计中的一种方法；
- 期盼通过每个阶段的局部最优选择，从而达到全局的最优；
- 有时候结果并不一定是最优；
题目
零钱兑换
左侧例子中，使用贪心算法的话，每次都会使用最大的硬币，所以得出了最优解。
右侧例子中，使用贪心算法的话，哪怕使用最大的硬币，但最终得出的不一定是最优解。
分发饼干
const findContentChildren = function (g, s) {
const sortFunc = function (a, b) {
return a - b;
}
g.sort(sortFunc);
s.sort(sortFunc);
let i = 0;
s.forEach(n => {
if (n >= g[i]) {
i += 1;
}
})
return i;
};
买卖股票的最佳时机 II
const maxProfit = function (prices) {
let profit = 0;
for (let i = 1; i < prices.length; i += 1) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
回溯法
- 回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
- 其基本思想是，在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
什么问题适合用回溯算法解决？
- 有很多路，这些路里，有死路，也有出路。通常需要递归来模拟所有的路。
题目
全排列
子集
剪枝/分支界限法
题目
N 皇后
N皇后 II
有效的数独
解数独
迭代法
迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法(或者称为一次解法)，即一次性解决问题。迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值，迭代法又分为精确迭代和近似迭代。比较典型的迭代法如“二分法”和”牛顿迭代法”属于近似迭代法。
二分法
使用二分查找的前提条件
- Sorted(数组必须是有序的，单调递增或者递减)
- Bounded(存在上下界，即数组边界)
- Accessible by index(能够通过索引访问，所以一般用数组，不会用链表)
function search(arr, target) {
let left = 0, len = arr.length, right = len - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return true;
} else if (arr[mid] < target) {
left = mid + 1;
} else if (arr[mid] > target) {
right = mid - 1;
}
}
return false
}
console.log(search([1, 2, 3, 4], 4));// true
console.log(search([1, 3, 2, 4], 2));// false
题目
x 的平方根
参考
百度百科
JavaScript 算法与数据结构
如何用数学家的思维指导生活、管理时间？
“量化”生活——新书《指导生活的算法：人类决策中的计算机科学》解读
若有收获，就点个赞吧
0 人点赞
