图论

最短路算法

DIjkstra朴素版：没有负权边的最短路O（n）;
Dijkstra堆优化版：将求最小值的过程有堆优化成O（logn）
bellman—ford算法：求可以有负权边的最短
spfa算法：对bellman-ford算法的优化

最小生成树算法

prim算法：选点
kruskral算法：选边

二分图算法

判断二分图：染色法
二分图的最大匹配：撬墙角算法

数据结构

栈

数组模拟先进后出的线性数据结构

单调栈：求数列下左边第一个比他大的数

队列

数组模拟先进先出的线性数据结构
单调队列：滑动窗口求最值

KMP

注意next数组的建立

tire字典树

son[][]保存儿子

并查集

注意fa[]数组的建立

堆

是一棵完全二叉树
利用二叉树的性质可以用一维数组保存

哈希

数字哈希：O（1）时间复杂度插入或删除数据
字符串哈希：前缀字符串哈希

基础算法

快速排序

找基准值大于的放右边，小于的放左边，再递归排序

归并排序

归并排序：先分区再合并
逆序对的数量：:

二分

数的范围：两个模版，一个是找左边区间的最后一个位置
数的三次方根；

高精度

高精度加法
高精度减法
高精度乘法
高精度除法

前缀和与差分

前缀和
子矩阵的和
差分：前缀和的逆运算
差分矩阵

双指针算法

两个指针出奇迹
最长连续不重复子序列
数组元素的目标和

位运算

二进制中1的个数 （lowbit）x&-x

区间合并

搜索

BFS

用队列暴力世界

Flood Fill

用一个st数组表示有没有遍历过此点
通常求连通块的个数

最短路模型

边权相同的时候
不用图论最短路算法

多源BFS

一开始吧所用的点都入队

最小步数模型

内部搜索

DFS

用递归栈暴力世界

DFS之连通性模型

DFS之搜索顺序

DFS之剪枝与优化

最优性剪枝
优化搜索顺序
排除等效冗余
记忆化搜索
可行性剪枝