算法大师兄

LincZero大约 3 分钟

算法大师兄

参考：

https://space.bilibili.com/1784235102，这里主要记的是《合集 · 热血编程》系列
https://space.bilibili.com/319521269，主要参考《合集 · 夜深人静写算法》、《合集 · 面试离谱题集》

一分钟记住所有算法

顺序表。顺序表和顺序表相关的算法主要有：
- 线性枚举
- 前缀
- 双指针
- 二分枚举
- 三分枚举
- 离散化
- 排序：冒泡排序、选择排序、插入排序、快速排序、希尔排序、归并排序、堆排序、基数排序、计数排序
- 模拟
- 贪心
链表
- 单向链表
- 双向链表
栈
- 后进先出栈（LIFO栈，Last Input, First Output）
- 单调栈
队列
- 先进先出队列（FIFO队列，First Input, First Output）
- 双端队列
- 单调队列
字符串
- kmp
- 字典树
- 马拉车
- AC自动机
- 后缀数组
- BM
树
- 二叉树
- 二叉搜索树
- AVL树
- 线段树
- 霍夫曼树
- 堆
- 红黑树
- 伸展树
- 左偏树
- Treap
- B+树
- 树链剖分
图
- 二分图
- 最短路
- 最小生成树
- 最近公共祖先
- 深度优先搜索
- 强连通分量
- 双连通分量
- 2-sat（读two-sat）
- 欧拉回路
- 哈米尔顿回路
- 迭代加深
- 广度优先搜索
- 拓扑排序
- A*
- 稳定婚姻
- 双向广搜
- 差分约束
- 并查集
- 哈希表
- 跳跃表
- 树状数组
- 最大流
动态规划（DP，Dynamic Programming）
- 递归
- 线性DP
- 记忆化搜索
- 背包问题
- 树形DP
- 区间DP
- 数位DP
- 状压DP
其他网友补充
- 图卷积、遗传算法、蚁群算法、粒子群算法、随机森林、XGBOOST、LightGBM、退火
- 斐波那契堆，cdq分治，kd树，扩展欧几里得，线性规划（单纯形算法）。还有计算机几何的一些算法（比如求求凸包直径的旋转卡壳）
- 重链剖分，长链剖分，实链剖分，Splay树，link cut tree，间隔打表，插头dp

枚举算法的优化

2552. 统计上升四元组open in new window

即找类似 1324 这样的四元组，ijkl

版本一：O(n^4)：

版本二：O(n^3)：先找位于中间k和j，再往外找i和l

版本三：O(n^2)，看不太懂，等学完其他再回来看

cnt记录类似132的三元组（利用空间，加速时间）。找类似 1324 这样的四元组，ijkl。
先定jl，再找ik。j，枚举第二个数再枚举第一个数
评论区好像说：
树状数组随便弄就行
有说能用归并排序统计二元组然后标记看作一个整体进行枚举或者离散化再来统计（可加前缀和优化）
有低于n^2的做法，线段树
用类似于KMP算法的原理解题，把已经获取到的4个数先缓存起来