算法与数据结构总结
本文基于 LeetCode 问题对算法与数据结构做总结，框架主要参考 OI wiki。文章关注算法的原理与背后暗含的思维直觉，且关注解决实际问题，对于经典算法一般不深究证明。
1. 算法基础
1.1. 复杂度
复杂度用于衡量算法的效率， 分为时间复杂度和空间复杂度。实际一般评估时间复杂度居多，它通常考虑算法运行所需要的基本操作数的数量。
在普通的笔记本上，运行 10^9 次简单循环需要 2s 左右，10^10 次则需要 20s 左右。
1.1.1. 渐进符号定义
渐进符号可形式化地描述算法的时间复杂度，它刻画的是算法运行时间随输入数据规模的增长而变化的趋势，因此忽略了对增长贡献较慢的部分（e.g. 多项式中的低阶项）。实际我们一般只关心算法运行的渐进上界，而不关心下界，渐进上界可用大 O 符号描述如下。该描述中，g(n) 是渐进上界。注意，这里的“=”与通常的用法并不相同。
1.1.2. 主定理※
主定理用于从理论上严格说明递归求解的总时间复杂度，详参 [1][4]。
1.2. 排序
Q: 为什么要关注排序的稳定性？
A: 稳定性在工程中很重要，尤其是在多关键字排序场景。比如，若要实现整体按分数排序，分数相同的按姓名排序，可先按姓名排序一遍，再按分数排序一遍，且第二遍排序保证稳定即可。
如果关注最坏时间复杂度，则归并排序与堆排序最优。归并排序实现简单，但堆排序空间效率更高。
1.3. 其它常见算法
1.3.1. 前缀和与差分
“前缀和”与“差分”是一对逆运算，即：假设对于序列 {a1, a2, ... , an}，求前缀和可得到序列 {b1, b2, ..., bn}，则对后者求差分即可得到前者。
前缀和的使用场景很好理解，最典型的就是求解任意的区间和。
差分往往和前缀和一起使用，最典型的是公交车上下客问题。如果按常规思路，需要更新每个区间中每个点的乘客计数，但差分思想通过维护每个站点的乘客数量变化情况，避免了大量的更新操作，只需最终计算一次前缀和即可得到每个站点的乘客数量。
1.3.2. 二分查找
二分查找用于在有序数组中查找某一元素，这是基础场景。另外还值得一提的一个应用场景是：找到满足某个条件的最值。
1.3.3. 状态压缩
状态压缩是指用一个整数来表示某集合的状态，一般适用于集合元素不多的情况（如 n <= 20）。状态压缩更多是一种技巧，实际运用时常与动态规划相结合，即状压 dp。需要注意的是，状压 dp 的本质是 dp 而非状压。在状压 dp 问题中，若不必求解所有的状态，可考虑带备忘的自顶向下求解方式（记忆化搜索），而非自底向上求解。
464: can-i-win（涉及博弈论，可用数学归纳法证明：能够建立完备搜索树的零和博弈在双方都状态最佳时必定在开局就已经决定胜、负或和局。数学归纳法真的太好用了！）
638: shopping-offers（记忆化搜索本质上是图的遍历，复杂度分析需要考虑点和边的规模）
1.3.4. 动态规划
动态规划的各类题型总结参 [1]。个人认为万变不离其宗，在问题的建模中，最重要的是定义清楚状态转移方程—— 我喜欢用更数学化一些的语言，称之为函数的递推关系式。
NOTE: 递推式中的自变量是有定义域的，在这个域之外的值对应的函数值需要单独求解。
3821: find-nth-smallest-integer-with-k-one-bits（周赛遇到的一道题，当时没做出来的原因就是没理清楚递推式的定义域）
2. 数据结构
2.1. 栈/队列/链表/哈希表
栈
3834: merge-adjacent-equal-elements（最近遇到的一道周赛题，当时用链表写得挺复杂，没想到用栈）
队列最典型的场景之一是图的 BFS。
2.2. 单调栈/单调队列
单调队列的典型应用场景是求滑动窗口的最值。
单调栈与单调队列的区别就是，单调栈只会在同一侧入栈和弹出，而单调队列的入队和出队分别在两侧。单调栈的典型应用场景是：在 O(n) 时间内为数组中每一个元素找到左/右侧第一个比它大/小的数。
2.3. 并查集
并查集用于维护不相交的集合，朴素实现下单次操作的最坏时间复杂度为 O(n)。路径压缩与按秩合并是两个常见的优化操作，使用其中一者可以使单次操作复杂度降到 O(log n) 左右，同时使用二者可达到接近 O(1) 的复杂度。
2.4. 树状数组
给定一个数组，若要求任意区间的元素和，可以通过预维护一个前缀和数组，达到 O(1) 的查询效率。但如果数组元素可变，则需要不断修改前缀和数组，每次修改的复杂度都达到了 O(n)。此时，树状数组派上了用场，它可以使查询和修改的复杂度都为 O(log n)。
树状数组的核心思想是通过一个额外的数组 c[i] 来维护不同的区间和，c[i] （下标均从 1 开始）维护的是原数组中 i-lowbit(i)+1 ~ i 的元素之和。其中，lowbit(i) 是 i 的二进制表示中最低位 1 代表的二进制值（可通过 i & -i 直接求得）。假设原数组长度为 8，根据 c 中元素维护的原数组元素集合的真包含关系，可以得到下图。
在上图中，恰好有：c[i] 的父节点为 c[i+lowbit(i)]（一般情形的严格证明略），故，
更新数组元素 arr[i] 时，只需更新 c[i] 与其所有祖先节点的值，逐个增加 diff 即可。
由于 c[i] 维护的是 i-lowbit(i)+1 ~ i 的元素之和，故，
1~i 的前缀和为 c[i] + c[i-lowbit(i)] + ... + c[1]。
模板题如下，
树状数组的一个经典应用场景是数组中求逆序对的数目，当数组元素的值域很大时，一般通过离散化操作将元素映射到一个较小的区间。因为求逆序对只关心数之间的大小，而不关心元素的值。此处“离散化”的含义是指将一个范围巨大或无限的值空间转换为一个范围很小的值空间。
3. 图论专题
3.1. DAG 与拓扑排序
定理：一个图是有向无环图，当且仅当该图可以进行拓扑排序。
拓扑排序要解决的是如何给一个 DAG（Directed Acyclic Graph，有向无环图）的所有节点排序。另一方面，根据上述定理，也可以用拓扑排序来判断一个有向图是否有环（不过 DFS 也能直接判断是否有环）。
拓扑排序只需持续地去掉入度为 0 的点和其关联的边即可（贪心策略）。只需稍加注意，即可做到每个点最多被处理一次，每个边最多被处理一次，即时间复杂度为 O(n+m)。
310: minimum-height-trees（有关图的中心，但与拓扑排序无直接关系，而是求解手段类似）
3.2. 最短路径
Floyd
Floyd 算法可求解图中所有顶点对之间的距离，其时间复杂为 O(n^3)，空间复杂度可优化到 O(n^2)，一般只能用于小规模的图（几百个顶点）。虽然使用场景有限，但 Floyd 算法运用动态规划思想，颇为精妙。
定义 dp(i, j, k) 为顶点 i, j 之间以不超过 k 的顶点为中间顶点的距离。状态转移方程为 dp(i, j, k) = min{dp(i, j, k-1), dp(i, k, k-1) + dp(k, j, k-1)}。根据该方程，在求解给定的 i, j, k 之前，要确保任意的 a, b 构成的 a, b, k-1 已被求解，故 k 应该在循环的最外层。在实现时，很容易把三维的状态数组优化到二维。（但二维数组毕竟是优化后的结果，直接看它难以体会核心的设计思想）
Dijkstra
Dijkstra 算法是一种单源最短路算法，可求解某一顶点到其它所有顶点的距离，朴素实现的时间复杂度为 O(n^2)，通过优先队列维护最近顶点的实现的时间复杂度为 O((m+n)log n)。一般后者的运行效率更高，但当边数足够大时，效率会劣于前者。
1514: path-with-maximum-probability（朴素实现会超时；更新后顶点直接入堆，延迟删除）
该算法使用贪心策略。定义已确定到目标顶点（记为 k）距离的集合 S，以及未确定距离的集合 Q。初始情形下 S 为空集，剩余顶点放入集合 Q，除了 k 本身的距离为 0，其它点的距离均记为 +infinity。每次从 Q 中取当前与 k 距离最小的顶点 v，将其从 Q 移入 S，并遍历 v 的所有不在 S 中的邻居，尝试更新它们到 k 的距离（松弛操作）。可以证明：算法在每次向 S 中添加顶点时，该顶点到 k 的距离已经确定（证明参 [4]）。
BFS
NOTE：对于不带权的图，可以通过 BFS 快速求出某顶点到其它所有顶点的距离，复杂度为 O(n+m)。
3.3. 最小生成树
G 的生成子图是指点集相同、边集为原图子集的图。这个概念自身并没有什么用，毕竟只有全部顶点、没有边的子图也是生成子图，它更多的是方便描述。最小生成树是一个特殊的生成子图，它满足：连通、无环、边数为 n-1。
Kruscal 算法
Kruscal 算法运用贪心策略求解。先将所有边集按升序排列，然后依次遍历这些边，每次将关联的顶点所在的集合（如果有）做合并，直到全部顶点被合入单一集合。算法需要查找和合并顶点所在的集合，因此需要使用并查集。算法的时间复杂度就是排序的复杂度 O(m log m)，并查集非主要贡献者，可以忽略。
3.4. 强连通分量（有向图）
强连通是有向图中才有的概念（无向图只有连通），指任意两个顶点之间都有可达路径。强连通分量（Strongly Connected Components, SCC）即极大的强连通子图。显然，在有向图中，环（包括自环）一定是一个强连通子图，因此环也一定在某个 SCC 上。
Tarjan 算法
Tarjan 算法可通过一次 DFS 求得全部的 SCC。算法维护两个关键变量：dfn[u] 和 low[u]，前者表示顶点 u 被访问的时间戳，后者表示顶点 u 的子树可通过一条返祖边回到的最早祖先节点。此外，算法还需维护一个栈，若遍历完 u 的所有邻居后，有 low[u] == dfn[u]，则栈中 u 与其上的节点均属同一个 SCC。
由于只需一次简单 DFS，故 Tarjan 算法的时间复杂度是 O(n+m)。
802: find-eventual-safe-states（有多种解法，但求 SCC 的方法更通用）
2036: longest-cycle-in-a-graph（最长环本身很难求，但本题有特殊约束）
3.5. 围长
围长是图的最小环的长度（最大环的长度称为周长）。求最小环有下面两种常见的方式，
1）（仅限无权图）按点遍历，分别以各顶点为起点做一次 BFS，复杂度为 O(n(n+m))
2）按边遍历，分别删除各边并求两端点之间的距离，通过 dijkstra 求距离的总复杂度为 O(m(n+m)log n)
3.6. 欧拉图
欧拉路径是经过图中每条边恰好一次的路径，欧拉回路是经过图中每条边恰好一次的回路。寻找欧拉路径的“七桥问题”被认为是图论的起点问题。如果图中存在一条欧拉回路，则称该图为欧拉图；如果不存在欧拉回路，但存在欧拉路径，则称该图为半欧拉图。
关于欧拉图，以下三个性质是等价的：
G 是欧拉图；
G 的所有顶点的度都是偶数（对于有向图，入度等于出度）；
G 可被分解为若干条不共边回路的并。
类似地，关于半欧拉图，有以下等价性质：
G 是半欧拉图；
G 具有恰好两个顶点的度为奇数，其余均为偶数（对于有向图，恰好有一个顶点出度比入度大 1，一个顶点出度比入度小 1，其余顶点出度均等于入度）；
G 可被分解为若干条不共边回路以及一条与回路不共边的路径的并；
Hierholzer 算法
Hierholzer 算法运用的是欧拉图/半欧拉图中的第三条等价性质，遍历完所有边和顶点之后即可得到欧拉回路/欧拉路径。以欧拉图为例，在已判定图为欧拉图的前提下，任意取一个顶点进行 DFS 搜索，直到找到一条回到该顶点的回路，并把遍历过的边删去（或标记）。然后从回路中选一个还有边的顶点，重复上述操作，不断将新找到的回路并入之前的子图，直到所有的边都被删去。
由于最终的效果是每条边、每个顶点恰好被遍历一次，故 Hierholzer 算法的复杂度是 O(n+m)。
332: reconstruct-itinerary（题目可暴搜求解，但 Hierholzer 才是杀手锏）
3.7. 哈密顿图
通过所有顶点恰好一次的回路/路径称为哈密顿回路/哈密顿路径，具有哈密顿回路的图称为哈密顿图，不具有哈密顿回路但具有哈密顿路径的图称为半哈密顿图。
哈密顿图没有欧拉图那样简单、可操作的等价判定条件，记录一个经典的充分条件如下：
定理：设 G 是顶点数 n >= 2 的简单无向图，若 G 中任意不相邻的顶点 u、v 均有 d(u) + d(v) >= n-1，则 G 中存在哈密顿路径。
推论：设 G 是顶点数 n >= 3 的简单无向图，若 G 中任意不相邻的顶点 u、v 均有 d(u) + d(v) >= n，则 G 中存在哈密顿回路，即 G 为哈密顿图。
3.8. 二部图
若 G 的顶点可以被划分为两个不相交的子集，使得每条边的两个端点都分别属于两个子集，则称 G 为二部图。二部图结构简单，许多在一般图上求解困难的优化问题在二部图上都可以高效地求解。
二部图的等价性质是：图 G 是可 2‑着色的，即可以用至多两种颜色给图的所有顶点染色，使得相邻顶点颜色不同（这里“至多”是技术性的，用于处理一些非典型情形）。基于该等价性质可以简单地判定某图是否为二部图。
3.9. 弦图※
任意长度大于 3 的图都有弦的图称为弦图。弦图是一种特殊的图，许多在一般图上 NP-Hard 的问题在弦图上都有非常优秀的时间复杂度表现。
leetcode 一般不考弦图，在此记录弦图主要是因为我的硕士论文研究的对象是弦图，题目为《关于弦图的中心与最长路》，主要结果如下。
4. 字符串专题
4.1. 字符串哈希
字符串哈希就是对给定的字符串计算哈希值，然后便可以依据数值判断两个字符串是否相等。常规的字符串判断是逐字符判断，复杂度为 O(n)，而通过预计算哈希值，判断相等的效率可提升至 O(1)。
多项式映射是最常使用的哈希计算方法，对于字符串 abc，可以按升幂顺序采用 a+bx+cx^2，也可以降幂顺序采用 ax^2+bx+c，类似于按字符位定义 x 进制数。后者在根据哈希值前缀和计算子串的哈希值时更方便。实际使用时，需要给定基数模数，比如令 base=131，mod=1e9+7，或者令 base=13331，mode=1e9+9。
NOTE: 1）计算哈希或前缀和要小心防止溢出，需频繁对 mod 求余；2）工程上一般通过增加一组 base 和 mod 做双哈希判断就足够了（更多卡哈希和防哈希冲突的细节参 [1]）。
1392: longest-happy-prefix（不用双哈希校验也能过）
4.2. 字典树
字典树（trie）就是一棵以字符为节点的树，可用于在一个大规模的字符串集合中查询某前缀是否存在（该场景无法通过维护子串的哈希来实现）。
4.3. KMP 算法※
KMP 算法也用于从主串中查找子串，它的最坏时间复杂度和字符串哈希相同，均为 O(n+m)，但无哈希冲突。
KMP 的基础是一个前缀数组 lps，数组元素 lps[i] 存储的是字符串 s[:i+1] 的最长相等前后缀长度，计算 lps 的技巧性较强，此处记录直接的应用题如下，时间复杂度为 O(n)。
KMP 最经典的应用场景就是子串匹配，记录题目如下。