学习算法用处总结
一、基础算法
1、RMQ(st表)
可以通过预处理的方法查询区间最大值和最小值
只适用于静态问题,时间复杂度O(nlog(n))
预处理f[i][j]表示前从i开始的长度为2j的区间最大值
二、数据结构
1、单链表和双链表
O(1)删除和插入
2、单调栈
维护一个单调递增或递减的序列,存储信息使得想要的结果
3、单调队列(滑动窗口)
维护窗口最值或者一个单调递增或递减的队列,某些程序会有大作用
4、kmp
O(n)匹配模式串和子串,维护重要的next数组
5、trie
存储数字或字符串出现次数,可以减少数据冗余,可以查询删除
可求最大异或和
6、可持久化trie
储存每一个字符串或数字的历史版本,可进行区间的查询,求区间的最大异或和
7、并查集
可以将两个集合合并成一个集合,可以维护集合的数量
可以查询集合是否在一个集合,时间复杂度O(n)
可以用并查集做一次的区间覆盖时间复杂度O(n)
维护多个集合的相互关系可以做很多事情
8、堆
维护一个大根堆或者小根堆,堆里面的数不是有序的,只是保证了根都是最小值或者最大值
9、哈希
开放寻址法和拉链法,一般情况O(1),但是可以卡到n2,尽量少用,是个概率算法
字符串哈希一般取131,99的概率不会碰到重复值
10、树状数组
可以在O(log(n))的时间复杂内修改和查询一个区间的值
11、线段树
可以实现单点,区间的修改和查询
有一个扩展的扫描线的应用,可以查询区域面积(长方形)
12、权值线段树
可以把一个区间分段,在区间长度O(log(n))下,维护一个区间的出现的树
13、可持久化线段树
存下每一个线段树的版本可以查询区间的第k小值
14、平衡树(treap)
插入数值 x
删除数值 x(若有多个相同的数,应只删除一个)
查询数值 x 的排名(若有多个相同的数,应输出最小的排名)
查询排名为 x 的数值
求数值 x 的前驱(前驱定义为小于 x 的最大的数)
求数值 x 的后继(后继定义为大于 x 的最小的数)
最主要的两个操作就是split(分裂)和merge(合并),可以按照权值分裂,也可以按照数的个数来分裂
15、AC自动机
相当于kmp的扩展用法,kmp是一个模式串匹配一个字串,AC自动机是一个模式串匹配一堆字串
AC自动机的有一个常数优化做法是trie图,时间复杂度是O(n)的
16、splay
17、树套树
18、块状链表
19、莫队
暴力区间查询的优化算法,通过分块将左端点分块,每次
左端点
块内移动不超过n12时间复杂度,左端点
块间移动总个数不超过n12块,右端点
每一移动不超过n,时间复杂度为O(n32)
20、树链剖分
21、动态树
22、DLX之精确覆盖问题
23、DLX之重复覆盖问题
24、左偏树
25、后缀数组
26、后缀自动机
27、点分治
28、点分树
29、CDQ分治
30、仙人掌
三、搜索与图论
BFS用于求最小值,第一次到达即为最小值
1、dfs & bfs
树的深度遍历、宽度遍历、字典序、N皇后等…
2、拓扑排序
判断是否有环
3、最短路算法
(1) Dijkstra:n2 算法就算起点s到终点e的距离 可以用堆优化加到O(nlog(n))
(2) bellman−ford: n∗m 用来做有边数限制的最短路,m为最短路
(3) spfa: 可以用来求最短路,可以判断负环,一般时间复杂度为O(n∗logn),最差为O(n∗m),v被更新的条件是u被更新
(4) Floyd: 现学的唯一一个多源最短路算法
4、最小生成树
(1) Prim: n2的时间复杂度,和Dijkstra非常像
(2) Kruskal: O(nlog(n)) 因为要排序
5、染色法判定二分图
没有单数环
6、匈牙利算法
二分图的最大匹配
7、双端队列bfs
用于边权为0和1的最短路算法
8、Flood Fill(走迷宫类型)
在线性时间内找到某个点的连通块
9、用bfs走最短路
bfs具有当每个点的距离相等时,第一次搜到就是最近点
四、数学知识
五、动态规划
1、背包问题
有 N 件物品和一个容量是 V 的背包。每件物品只能使用次数在每个题目不一定。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
2、线性DP
数字三角形,最长上升子序列,最长公共子序列,最短编辑距离啥的
3、区间DP
三层循环,第一层为长度,第二层为枚举区间,第三层枚举分界点
4、单调队列优化DP
5、斜率优化DP(凸包优化DP)
维持好一个斜率的关系就好
六、贪心
1、区间问题
可根据区间左端点或右端点排序,贪心的选择,使其得到想要的结果
2、Huffman树
合并果子问题,把一个问题分成多个子问题,子问题达到最优解时,证明两个子问题的最优解相加就是问题的最优解
3、绝对值不等式
货仓选址问题,在多个位置之间选择一个位置,使得所有地址到达此位置之和最小
4、推公式
考虑两个位置交换前和交换后,对其他位置的价值不产生影响,考虑交换前后最优解