整理数据结构与算法相关代码，供复习查阅。

数组A[l, r]被划分为两个（可能为空）子数组A[l, q-1]和A[q+1, r]， 使得A[l, q-1]中每一个元素都小于等于A[q]，而A[q]也小于等于A[q+1, r]中的每个元素。 递归地在每个子数组继续进行上述过程。

将输入数组建成小根堆，每次弹出堆顶元素。

递归地对左右两个子序列进行归并排序，然后将两个有序序列归并起来，得到完全有序的序列。

当知道待排序关键词的更多知识时，例如分布的范围，就能构造出非基于关键词比较的排序算法，而且能在最坏情况下达到线性时间。

对每一个输入元素x，确定小于x的元素个数，利用这一信息，就可以直接把x放在它的输出数组的位置上。

先按最低位有效位进行排序，再按照次低位有效位进行排序，以此类推。

假设输入服从均匀分布； 将值分布区间划分为n个相同大小的子区间（称为桶），然后将n个输入数分别放到各个桶中，因为输入数据是均匀的，所以一般不会出现多个数据落在同一个桶中的情况；先对每个桶中的数进行排序，然后遍历每个桶，按照次序把每个桶中元素列出来即可。

• 优先级队列：O(nlogk)
• Partition：O(n)

把图中的所有顶点分两组，第一组：已求完最短路径的顶点，第二组：未求完最短路径的顶点，按最短路径长度递增的顺序逐个把第二组的顶点加到第一组。

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) }

适用于边稀疏图的最小生成树算法，复杂度是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， 每件物品只能使用一次，

解： $dp(i, j)$表示前i件物品放入容量为j的背包的最大收益

$$dp(i, j) = \max {dp(i - 1, j), dp(i - 1, j - v[i]) + w[i]}$$

第 i 种物品的体积是 vi，价值是 wi， 每种物品都有无限件可用。

解： $dp(i, j)$表示前i种物品放入容量为j的背包的最大收益

$$ dp(i, j) = \max { dp(i, j), dp(i, j - v[i]) + w[i] } $$

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

解：

• 方法一：直接当成01背包问题求解，复杂度 $O(NVS)$
• 方法二：二进制优化的多重背包，将多重背包问题转化为01背包问题。复杂度$O(NVlogS)$
• 方法三：单调队列优化的多重背包，复杂度$O(N*V)$

物品一共有三类：

• 第一类物品只能用1次（01背包）；
• 第二类物品可以用无限次（完全背包）；
• 第三类物品最多只能用 si 次（多重背包）；

每种体积是 vi，价值是 wi。

解： 使用二进制优化的方法将多重背包转化为01背包，然后同时解01背包和完全背包。

每组物品有若干个，同一组内的物品最多只能选一个。 每件物品的体积是 vik，价值是 wik，其中 i 是组号，k 是组内编号。

解： $dp(i, j)$表示前i组物品放入容量为j的背包的最大收益

$$ dp(i, j) = \max { dp(i - 1, j), \max_k {dp(i - 1, j - v[i][k]) + w[i][k] } } $$

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。 每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

解： $dp(i, j, k)$表示前i个物品放入容量为j，承重为k的背包的最大收益。

$$ dp(i, j, k) = \max { dp(i - 1, j, k), dp(i-1, j-v[i], k-m[i]) + w[i] } $$

时间复杂度：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滑动窗口最大值
• 多重背包优化

• 二分查找
• 排序
• 优先级队列