算法基础

数组(擅长查询): 内存连续地分配
增删数组因为会影响到剩余的元素, 因此时间复杂度为 O(n)

链表(擅长增删): 内存分配不连续, 每个节点记录下一个节点的地址, 若每个节点记录上一个和下一个节点地址则为双向链表
增删链表节点只需要修改受影响节点的上下节点地址, 因此时间复杂度为 O(1)

栈
函数的调用栈
函数的嵌套执行是一个入栈(执行时)/出栈(返回时)过程 (影响栈的总高)
调用栈会保存同层级未调用的函数, 等待之前函数的入/出栈过程完成后执行 (不影响栈的总高)

图: 节点之间具有相互指向的关系
有向图、无向图(相当于两个节点相互指向的有向图)
var graph = {
a: [b, c],
b: [c],
c: [d],
}
广度优先是用于图的一种查找算法, 可解决两类问题
能否到达目的地
到达目的地的最短距离
广度优先伪算法：（基于队列）
1、以起点能一步达到的节点生成队列
2、队列弹出一个值, 判断其是否为 d, 若否, 将其能一步达到的节点插入队列
3、重复2, 直到找到 d 或者队列为空
在这个过程中可能会遇到同一节点入队多次, 应当标记其是否被检查来避免无限循环, 或用列表来存储已检查过的节点

狄克斯特拉算法 (适用于有向无环图, 不适用于有负权重的边)
广度优先仅能找出到达目的地的最少段数, 但在有权重的情况下需要用到狄克斯特拉算法, 基本思路为
1、从起点开始找出最便宜的下一节点
2、检查是否有到达该节点邻居节点的更快路径(上文中 b和c 即为邻居节点)
3、重复操作, 直到更新所有的节点权重

贝尔曼-福德算法 (可适用于负权重的边)

树: 一种特殊的图, 只能单向, 不能回指
二叉树的非递归遍历
先序: 根节点入栈, 而后每次循环(先出栈, 访问该节点, 而后右/左节点分别入栈), 直到栈空
中序: 所有左子节点入栈, 出栈, 访问该节点, 如果该节点有右子节点, 则对其重复之前操作
后序: 根节点入栈, 循环出栈, 判断是否已标记, 若已标记则访问, 若未标记则将其右/左节点入栈, 直至无叶节点时标记

hash表: 类似JS中的对象, 可以通过key找到value

算法复杂度
时间复杂度, 运算的次数
空间复杂度, 占用的内存空间

递归
找出基线条件
缩小问题的规模使其符合基线条件

尾递归

快速排序和合并排序
快速排序
时间复杂度平均是 O(nlogn)
最坏情况每次都选择有序数组的第一个值作为基准值 O(n2)
最佳情况每次都选择有序数组的中间值作为基准值 O(nlogn)
归并排序
时间复杂度稳定是 O(nlogn)
虽然两者的表示法相同, 但快排的常量基数更小, 因此速度会相对更快, 但快排的速度并不稳定(依赖于基准值), 极端情况下可达到 O(n2)

贪心算法：每次寻找局部最优解, 他可能不是总最优解, 但会很接近

动态规划：先解决子问题, 再逐步解决大问题, 动态规划往往都可以用表格来表示, 但没有一个固定的公式可以使用

走台阶问题：共 N 级台阶, 每次走 1-2 级, 共有几种方案
思路: 分别计算爬上 n-1 和 n-2 的方法数并相加, 即 dp(n) = dp(n-1) + dp(n-2) , 然后遍历计算出 dp(0) ~ dp(n) 的值, 也可以用网格表示
设 n = 5
阶数 0 1 2 3 4 5
方案数 1 1 2 3 5 8
实现:
function climbStairs(n) {
const dp = [1,1] // dp[0] 和 dp[1] 都只有一种方案, 因此从2开始遍历
for(let i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}

背包问题: 包容量4磅, 吉他1磅1500, 电脑3磅2000, 音响4磅3000, 求价值最大解
思路: 计算单元格的公式: cell[i][j] = Math.max( cell[i-1][j], 当前产品价值 + cell[i-1][j-当前产品重量] )
1 2 3 4
吉他 1500 1500 1500 1500
电脑 1500 1500 2000 3500
音响 1500 1500 1500 3000

最长公共子串 ('fort', 'fosh') => 2
思路: 如果行列两个字母相同, 当前值为左上角邻居值+1
f o r t
f 1 0 0 0
o 0 2 0 0
s 0 0 0 0
h 0 0 0 0

最长公共子序列 ('fort', 'fosh') => 2 ('fish', 'fosh') => 3
思路: 如果行列两个字母相同, 当前值为左上角邻居值+1, 如果行列两个字母不同, 当前值为 Math.max(上邻居值, 左邻居值)
f o r t f i s h
f 1 1 1 1 f 1 1 1 1
o 1 2 2 2 o 1 1 1 1
s 1 2 2 2 s 1 1 2 2
h 1 2 2 2 h 1 1 2 3

无重复字符的最长子串 "abcabcbb" => 3
思路：滑动窗口, 使用左右指针(left, right)维护当前子串,
不断判断 right+1 是否在当前子串内,
如是, 则从左侧开始缩减(left+1)直到 right+1 不在当前子串内
否则将其加入当前子串, right+1
function getSub(str) {
let left = 0
let right = 1
let result = 0
while(right < str.length) {
if(str.slice(left, right).indexOf(str[right]) === -1) {
right++
} else {
left++
}
result = Math.max(result, right-left+1)
console.log(left, right, result)
}
return str.length < 2 ? str.length : result
}
getSub("771234123451")