数据结构

顺序存储

数组

时间复杂度：随机访问O1 插入On（头插尾插 O1）删除 On 可通过缓存加速

链式存储

链表，跳表

单链表
- 跳表：对标平衡二叉树和二分查找，只能用于有序的链表
- 时间复杂度：不支持随机访问，访问On 插入O1 删除 O1
- 跳表的时间复杂度：访问，删除，插入 logn —索引的高度logn 空间复杂度 On
双向链表
- 每个节点都多个指向前一个节点的指针
循环链表
- 尾节点指向头节点

线性存储

队列

普通队列
- 时间复杂度：添加和删除 O1 先进先出，查找0n
- LRU ，有限资源
双端队列
- 入口出口都可以进站出战
优先队列
- 优先队列插入01，取出logn 按优先级取出（heap 二叉搜所树实现）

栈

时间复杂度：添加和删除 O1 先进后出，查找0n
括号匹配表达式计算，浏览器前进后退

非线性存储

大顶堆，小顶堆（完全二叉树，斐波那契，数组）

可以快速查找最大或者最小值的数据结构
时间复杂度：find-max O1 delete max O1 insert logn 或者O1 这是斐波那契
代码实现

// JavaScript
class BinaryHeap{
constructor(compare) {
this.data = [];
this.compare = compare;
}

insert(value) {
this.insertAt(this.data.length, value);
}

insertAt(index, value) {
this.data[index] = value;
// 对比当前节点与其父节点，如果当前节点更小就交换它们
while (index > 0 && this.compare(value, this.data[Math.floor((index - 1) / 2)]) < 0) {
this.data[index] = this.data[Math.floor((index - 1) / 2)];
this.data[Math.floor((index - 1) / 2)] = value;
index = Math.floor((index - 1) / 2);
}
}

delete(index) {
if (this.data.length === 0) return;

let value = this.data[index];
let i = index;
// fix heap
while (i < this.data.length) {
let left = i 2 + 1;
let right = i 2 + 2;
// 没有左子节点
if (left >= this.data.length) break;
// 没有右子节点
if (right >= this.data.length) {
this.data[i] = this.data[left];
i = left;
break;
}
// 比较左右子节点的大小，更小的补到父节点
if (this.compare(this.data[left], this.data[right]) < 0) {
this.data[i] = this.data[left];
i = left;
} else {
this.data[i] = this.data[right];
i = right;
}
}
// 查看最后的空位是不是最后的叶子节点
if (i < this.data.length - 1) {
this.insertAt(i, this.data.pop());
} else {
this.data.pop();
}
return value;
}

printHeap() {
console.log(“nHeap = “);
console.log(this.data);
}
}

let maxHeap = new BinaryHeap((a, b) => b - a);
maxHeap.insert(10);
maxHeap.insert(4);
maxHeap.insert(9);
maxHeap.insert(1);
maxHeap.insert(7);
maxHeap.insert(5);
maxHeap.insert(3);

maxHeap.printHeap();
maxHeap.delete(5);
maxHeap.printHeap();
maxHeap.delete(2);
maxHeap.printHeap();

二叉树搜索树

概念：左子树都小于根节点右子树都大于根节点，不是左儿子右儿子每层都一样
深度优先
- 前序遍历：根左右
- 后序编列左右根
- 中序遍历左根右，通过中序便利可以判断前一个值必须小于pre 值来验证是一颗二叉搜索树
广度优先
形态
- 平衡二叉树
  - 红黑树，AVL树
- 完全二叉树堆
- 满二叉树

多路查找树

B树
B+树
2-3树
2-3-4树

map

key-value
操作 get has set size

set

value 不重复的元素
操作 add has delete

hash

hash 也称为散列表根据关键码值而进行直接访问的数据结构，它们通过把关键妈值映射道表中的位置来访问记录，以提高快速查找。映射函数叫散列函数
时间复杂度：添加和删除和查找 O1 最坏的情况 0n 如果哈希函数不好一样存放的位置一样就会成为链表，如果时间复杂度会退化为On

图

有环的树就是图
拓扑排序
最短路径
关键路径
最小生成树
二分图
最大流

复杂度分析

时间复杂度

分析
- 最好
- 最坏
- 平均
- 均摊
常见复杂度
- 散列表O1
- logn 二叉树和二叉搜索树
- On 大多数遍历
- On^2 双层遍历
- 2^n 递归

空间复杂度

原地操作就是O1
开辟线性辅助结构就是On

算法

排序

0N^2
- 冒泡
  - 嵌套循环，每次查看相邻的元素如果逆序，则进行交换
- 选择
  - 每次选择最小值，然后放在待排序数组的起始位置
- 插入
  - 从前到后逐步构建有序序列，对于未排序数据，在以排序序列中从后向前扫描，找到相应位置插入
- 希尔
nlogn
- 归并
  - 1.把长度为n的输入序列分为长度为n/2的子序列
  - 对这两个子序列采用归并排序
  - 讲两个排序好的子序列合并成一个最终的排序序列
- 快排
- 堆排序
On
- 基数排序
  - 按照低位先排序然后收集，在按照高位排序，再收集，依次类推，直到最高位，有时候有些属性是有优先级顺序的，线按低优先排序，再按高优先级排序
- 计数排序
  - 计数排序要求输入的数据必须是有确定范围的整数，将输入的数据值转化为键存储在额外开辟的数组空间中，然后以此把计数大于1的填回原数组
- 桶排序
  - 假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶在进行分别的排序

查询

线性表查找
树结构查找
散列表查找

搜索

深度优先搜索 bfs

//JavaScript
const bfs = (root) => {
// 队列也是放入root
let result = [], queue = [root]

while (queue.length > 0) {

let level = [], 
n = queue.length

// 深入便利

for (let i = 0; i < n; i++) {
  let node = queue.pop()
  level.push(node.val) 
  if (node.left) queue.unshift(node.left)
  if (node.right) queue.unshift(node.right)
}
result.push(level)

}
return result
};

广度优先搜素 dfs

//JavaScript
const visited = new Set()
const dfs = node => {
// 浏览过了
if (visited.has(node)) return
visited.add(node)
// 左右一层一层
dfs(node.left)
dfs(node.right)
}

void dfs(Node* root){
map<int, int> visited;
if(!root) return ;

stack<Node*> stackNode;

// 放入
stackNode.push(root);
// 判断
while (!stackNode.empty()) {
Node* node = stackNode.top();
stackNode.pop();
///弹栈
if (visited.count(node->val)) continue;
// 添加
visited[node->val] = 1;

  // 将剩余的放入
  for (int i = node->children.size() - 1; i >= 0; --i) {
      stackNode.push(node->children[i]);
  }

}

return ;

}

A*启发式搜索

算法思想

递归

function recursion(level,params){

    // 终止条件
if(level> MAX_LEVEL){
    return
}
// 当前层的逻辑
process（level，params）

// drill down  递归 处理
recursion（level+1，prams）

/ clean current level status if needed

}

避免人肉递归，最小子问题，无非就是if else while for ，数学归纳法

分治

const divide_conquer = (problem, params) => {
```
// 递归终止条件
```
if (problem == null) {
```
process_result

return
```
}
// process current problem 处理当前逻辑
subproblems = split_problem(problem, data)
// 分部获取数据
subresult1 = divide_conquer(subproblem[0], p1)

subresult2 = divide_conquer(subproblem[1], p1)

subresult3 = divide_conquer(subproblem[2], p1)

…

/ /merge

result = process_result(subresult1, subresult2, subresult3)

// revert the current level status

}

回溯

result = []
def backtrack(路径, 选择列表):

if 满足结束条件:
    result.add(路径)
    return

for 选择 in 选择列表:
    做选择
    backtrack(路径, 选择列表)
    撤销选择

能够回退

剪枝
贪心
- 只关系眼巴前的问题，每次都是解决当前状态最好和最优的选择，从而希望最后获取最好结果
- 简单题目
  - 455 分发饼干
  - 1005 k次取反后最大化的数组和
  - 860 柠檬找零
- 中等题目
  - 序列问题
    - 376 摆动序列
    - 738
  - 贪心解决股票问题
    - 股票 122 714
  - 两个纬度权衡问题
    - 糖果 135
    - 根据身高重建队列 406
- 有点难度
  - 区间问题
    - 跳跃游戏
    - 用最少的剑射爆气球
    - 无重叠区间
    - 划分字母区间
    - 合并区间
  - 最大自序和
  - 加油站
  - 监控二叉树
- 与动态规划的区别
  - 贪心算法对每一步字问题解决方案做出选择，然后不能回退
  - 动态规划，保存每一步的解决方案，并根据以前的结果对当前进行选择，可以回退
二分查找

/ JavaScript /
let left = 0, right = len(array) - 1
while (left <= right) {
let mid = (left + right) >> 1
if (array[mid] === target) { /find the target/; return }
else if (array[mid] < target) left = mid + 1
else right = mid - 1
}
- 单调递增单调递减
- 存在上下界
- 能够通过索引访问
动态规划
- 储存中间状态opt【】
- 最优子结构 opt【n】= best_opt(opt(n-1), opt(n-2))
- 递推公式
牛顿迭代法
- while(r*r>x){r=(r+x/r)/2|0}

字符串匹配

朴素
RK
BM
KMP
Trie
Ac自动机
后缀数组

位运算

常见的公式

布隆过滤器

多个hash 映射在多个位上
不存在100%准确
存在不一定正确

LRU cache

散列表+双向链表
O1的查找与插入