整理数据结构与算法相关代码,供复习查阅。
数组A[l, r]被划分为两个(可能为空)子数组A[l, q-1]和A[q+1, r], 使得A[l, q-1]中每一个元素都小于等于A[q],而A[q]也小于等于A[q+1, r]中的每个元素。 递归地在每个子数组继续进行上述过程。
将输入数组建成小根堆,每次弹出堆顶元素。
递归地对左右两个子序列进行归并排序,然后将两个有序序列归并起来,得到完全有序的序列。
期望时间复杂性 | 最坏时间复杂性 | 最好时间复杂性 | 是否稳定 | |
---|---|---|---|---|
快速排序 | O(nlogn) | O(n^2) | O(nlogn) | 不稳定 |
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | 稳定 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | 不稳定 |
插入排序 | O(n^2) | O(n^2) | O(n) | 稳定 |
冒泡排序 | O(n^2) | O(n^2) | O(n) | 稳定 |
选择排序 | O(n^2) | O(n^2) | O(n^2) | 不稳定 |
当知道待排序关键词的更多知识时,例如分布的范围,就能构造出非基于关键词比较的排序算法,而且能在最坏情况下达到线性时间。
对每一个输入元素x,确定小于x的元素个数,利用这一信息,就可以直接把x放在它的输出数组的位置上。
先按最低位有效位进行排序,再按照次低位有效位进行排序,以此类推。
假设输入服从均匀分布; 将值分布区间划分为n个相同大小的子区间(称为桶),然后将n个输入数分别放到各个桶中,因为输入数据是均匀的,所以一般不会出现多个数据落在同一个桶中的情况;先对每个桶中的数进行排序,然后遍历每个桶,按照次序把每个桶中元素列出来即可。
- 优先级队列:O(nlogk)
- Partition:O(n)
基于Partition函数的思路 | 基于堆或者红黑树的思路 | |
---|---|---|
时间复杂度 | O(n) | O(nlogk) |
是否需要修改输入数组 | 是 | 否 |
是否适用于海量数据 | 否 | 是 |
把图中的所有顶点分两组,第一组:已求完最短路径的顶点,第二组:未求完最短路径的顶点,按最短路径长度递增的顺序逐个把第二组的顶点加到第一组。
const int MAXN = 1000;
struct edge{
int to, cost;
}
vector<edge> G[MAXN]; // 图的邻接表表示
int d[MAXN]; // d[i] 是从s到i的最短距离
// 使用优先级队列优化
typedef pair<int, int> P; // second是顶点编号,first是s到该顶点的最短距离。
priority_queue<P, vector<P>, greater<P>> que;
dp(i, v)表示从起始点开始经过不超过i条边到v的最短路径长度
dp(i, v) = min{ dp(i - 1, v), min{ dp(i - 1, u) + d[u][v] } }
dp(k, i, j) 表示从i到j,中间只可以经过{0, 1, ..., k}这些顶点的最短路径长度
dp(k, i, j) = min{ dp(k - 1, i, k) + dp(k - 1, k, j) }
解决问题 | 复杂度 | 方法 | 特点 | |
---|---|---|---|---|
Dijkstra | 单源最短路径 | O(E*logV) | 贪心方法 | 边权非负 |
Bellman-Ford | 单源最短路径 | O(E*V) | 动态规划 | 可以检测负环 |
Floyd | 任意两点最短路径 | O(V^3) | 动态规划 | 不允许有负环 |
适用于边稀疏图的最小生成树算法,复杂度是O(E*log(E))
Kruskal算法按照边权值从小到大顺序查看一遍,如果不产生环(重边也算环),就把当前这条边加入到生成树中。
适用于边稠密图的最小生成树算法,复杂度是O(V^2)
优先级队列优化,复杂度是O(E*log(V))
初始化只有一个顶点的树X,然后贪心地选取X和其他顶点之间相连的最小权值的边,并把它加到X中;不断这个操作,直到把所有顶点纳入X中,就得到最小生成树。
- 先序遍历(Preorder)
- 中序遍历(Inorder)
- 后续遍历(Postorder)
- 层次遍历
- 先序+中序可重构树
- 后续+中序可重构树
- 先序+后续不可重构树
- 链表反转
- 链表排序
- 链表判环 & 找环入口: 弗洛伊德判环算法(龟兔赛跑算法)
在字符串T中找出字符串P出现的每一个位置,时间复杂度O(n+m)
有 N 件物品和一个容量是 V 的背包,求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
第 i 件物品的体积是 vi,价值是 wi, 每件物品只能使用一次,
解:
第 i 种物品的体积是 vi,价值是 wi, 每种物品都有无限件可用。
解:
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
解:
- 方法一:直接当成01背包问题求解,复杂度 $O(NVS)$
- 方法二:二进制优化的多重背包,将多重背包问题转化为01背包问题。复杂度$O(NVlogS)$
- 方法三:单调队列优化的多重背包,复杂度$O(N*V)$
物品一共有三类:
- 第一类物品只能用1次(01背包);
- 第二类物品可以用无限次(完全背包);
- 第三类物品最多只能用 si 次(多重背包);
每种体积是 vi,价值是 wi。
解: 使用二进制优化的方法将多重背包转化为01背包,然后同时解01背包和完全背包。
每组物品有若干个,同一组内的物品最多只能选一个。 每件物品的体积是 vik,价值是 wik,其中 i 是组号,k 是组内编号。
解:
有 N 件物品和一个容量是 V 的背包,背包能承受的最大重量是 M。 每件物品只能用一次。体积是 vi,重量是 mi,价值是 wi。
解:
时间复杂度:O(logn)
- 计算整数x的n次幂
- 计算矩阵A的n次幂
f(0) = 0
f(1) = 1
f(n) = f(n - 1) + f(n - 2)
方法一:动态规划
时间复杂度:O(n)
dp(n) = dp(n - 1) + dp(n - 2)
方法二:矩阵快速幂
时间复杂度:O(logn),但是隐含的时间常数较大。
n个人编号0,...,n-1围成一圈,顺时针从1开始报数,每次报到m的人被杀掉并移出去,
然后从下一个人开始报数,直到剩余一个人;求最后活着的人的编号。
解:
dp(i)表示一共i个人最后活着的人的编号
dp(1) = 0
dp(i) = (dp(i - 1) + m) % i
- 判断n是否是素数:只需判断n能否被2-sqrt(n)之间的数整数
- 枚举n以内的素数:埃氏筛法
求两个非负整数a和b的最大公约数
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
解x和y,使得 ax + by = gcd(a, b)
定理:一定存在整数x和y使得ax+by=gcd(a,b)
int extgcd(int a, int b, int& x, int& y) {
int d = a;
if (b != 0) {
int x1, y1;
d = extgcd(b, a % b, x1, y1);
x = y1;
y = x1 - a / b * y1;
} else {
x = 1;
y = 0;
}
return d;
}
m1、m2、m3两两互质,a1、a2、a3都是整数,则下列同余方程组有解,且在模m1m2m3下解唯一;
x = a1 (mod m1)
x = a2 (mod m2)
x = a3 (mod m3)
解:
取c1、c2、c3使得下面式子成立
l1 = m2 * m3 * c1 => l1 = 1 (mod m1)
l2 = m1 * m3 * c2 => l2 = 1 (mod m2)
l3 = m1 * m2 * c3 => l3 = 1 (mod m3)
则,
x = a1 * l1 + a2 * l2 + a3 * l3 即为所求解。
并查集是一种用来管理分组情况的数据结构。 并查集可以高效地进行如下操作:
- 查询元素a和元素b是否属于同一组
- 合并元素a和元素b所在的组
线段树(Segment Tree)擅长处理区间
树上每个节点都维护一个区间。根节点维护整个区间,每个节点维护的是父亲的区间二等分后的其中一个子区间。
例如,建立给定数列a[0...n-1]的线段树,可以在O(logn)时间内完成如下两种操作:
- 给定s和t,求a[s...t]的最小值
- 给定i和x,把a[i]的值改成x
树状数组(Binary Indexed Tree, BIT)是能够O(logn)复杂度下完成下述操作的数据结构
给定一个初始值全为0的数列 a1, a2, ..., an
- 给定i,计算a1 + a2 + ... + ai
- 给定i和x,执行ai = ai + x
Trie又被称为字典树。
树的每个条边代表一个字符,从根到叶结点经过的边组成的字符序列构成一个单词。
- 出现“让最大的最小”或“让最小的最大”字样,首先想到二分答案。
- 如果直接求解答案困难,但是判断一个值是不是答案很容易,考虑二分答案来做。
反复地推进区间的开头和结尾,来求取满足条件的最小区间。
应用:
- 长度最小的子数组
深度优先遍历:栈/递归 宽度优先遍历:队列
应用:
- 柱状图的最大矩形区域
应用:
- K滑动窗口最大值
- 多重背包优化
- 二分查找
- 排序
- 优先级队列