面试高级算法梳理笔记

1.1 说明

本篇为《挑战程序设计竞赛（第2版）》读书笔记系列，旨在：

• 梳理算法逻辑
• 探索优化思路
• 深入代码细节

1.2 目录

原文首发于个人博客Jennica.Space，按算法难度划分为初中高三个级别，详细目录及链接如下：

• 初级篇

  1. 穷竭搜索
  2. 贪心
  3. 动态规划
  4. 数据结构
  5. 图论
  6. 数论

• 中级篇

  1. 二分搜索
  2. 常用技巧
  3. 数据结构（二）
  4. 动态规划（二）
  5. 网络流
  6. 计算几何

• 高级篇

  1. 数论（二）
  2. 博弈论
  3. 图论（二）
  4. 常用技巧（二）
  5. 智慧搜索
  6. 分治
  7. 字符串

1.3 题解

配套习题及详解同步发布在GitHub仓库acm-challenge-workbook，持续更新。预计在2017年3月完成，欢迎watch。习题难度从国内机试、国外IT名企面试到ACM地区赛不等，吃透算法习题册，应聘足以。

1.4 题库

• Google Code Jam（GCJ）
• Peking University Online Judge（POJ）
• CodeForces（CF）
• LeetCode（LC）
• Aizu Online Judge（AOJ）

2.1 穷竭搜索

2.1.1 核心思想

1. 深度优先搜索（DFS）：从某个状态开始，不断转移，直至无法转移，回退到前一步，再继续转移到其他状态，直到找到最终解。通常采用递归函数或者栈（Stack）来实现。
2. 宽度优先搜索（BFS）：从初始状态开始，总是先搜索至距离初始状态近的状态。每个状态都只经过一次，因此复杂度为O(状态数*转移方式数)。通常采用循环或队列（Queue）实现。

2.1.2 优化细节

1. 特殊状态枚举：可行解空间多数可采用DFS，但当其比较特殊时，可简短地实现。
   • 全排列使用STL中的next_permutation
   • 组合或子集使用位运算
2. 剪枝：明确知道从当前状态无论如何转移都不会存在解的情况下，不再继续搜索而是直接跳过。
3. 栈内存与堆内存：
   • main函数中的局部变量存储在栈内存中，统一分配后不再扩大，影响栈深度，与机器设置有关。通常，C++中执行上万次递归是可行的。
   • new或malloc的分配的是堆内存，全局变量存储在堆内存中，使用全局变量代替局部变量可减少栈溢出的风险。
4. 加深深度优先搜索（IDDFS）：初始的DFS递归深度限制为1，在找到解之前不断增加递归深度。

2.2 贪心

2.2.1 核心思想

1. 贪心算法：遵循某种规律，不断贪心选取当前最优策略。
2. 贪心证明：
   • 与其它选择方案相比，该算法并不会得到更差的解（归纳法）
   • 不存在其他的解决方案（反证法）

2.3 动态规划

2.3.1 核心思想

1. 动态规划（DP）：通过定义某种最优子状态，进行状态间转移达到最终解。
2. 记忆化搜索：将重复状态通过标记降低复杂度。
3. 多种形式的DP：搜索的记忆化或利用递推关系的DP，或从状态转移考虑的DP。状态定义和循环顺序都会影响复杂度。

2.3.2 优化细节

1. 使用memset初始化
2. 重复循环数组
3. dp仅bool是一种浪费
4. 根据规模改变DP对象

2.3.3 经典模型

1. 背包问题（01背包，完全背包）
2. 最长子序列（LCS，LIS）
3. 划分数（第二类Stirling数，Bell数）

2.4 数据结构

2.4.1 核心思想

1. 优先队列：包含两类操作插入和取值。插入一个数值，获取最小值并删除。堆可高效实现优先队列。
2. 堆：儿子的值一定不小于父亲的值的一种二叉树。插入时先在堆末插入，不断上移直至无大小颠倒。取值时，删除最小值，将堆末节点复制到根，不断下移直至无大小颠倒。插入和取值复杂度都为O(logn)。
3. 二叉搜索树：对所有节点都满足，左子树上的所有节点比自己小，右子树上的所有节点比自己大。插入与查询类似二分，删除时将删除节点左子树最大值或右子树（无左子树时）上移，每种操作复杂度都为O(logn)。
4. 并查集：一种管理元素分组情况的数据结构。可以查询两个元素是否同组，可以合并两组元素，但不能进行分割操作。一次操作复杂度为阿克曼函数反函数a(n)，比O(logn)快。

2.4.2 优化细节

1. 平衡二叉树（AVL）：当左右子树深度差超过1时，将更深的子树旋转上移，达到整棵树的平衡，避免二查搜索树退化后复杂度升至O(n)。
2. 路径压缩：并查集向上的递归操作中，沿途所有节点一旦向上走到一次根节点，就把其到父亲的边直接连向根。
3. 并查集的同组：广义可表示组内所有元素代表的情况同时发生或不发生。
4. STL标准库：
   • 优先队列：priority_queue（默认根为最大值）
   • 二查搜索树：set（集合）、map（键和值对应）、multiset和multimap（可存放重复键值）

2.5 图论

2.5.1 核心思想

1. 图：顶点集合为V、边集为E的图记作G=(V,E)，从u到v的边记作e=(u,v)。根据边是否有向分为有向图和无向图，根据是否有环分为有环图和无环图。图可由邻接表和邻接矩阵两种方式表示。
2. Bellman-Ford算法（单源最短路）：记录起点到每个点i的最短距离d[i]，用所有的边条件持续更新d[i]，直到每个d[i]都已经为最小无法更新。图可包含负权边，包含负环的判断方法为将所有d[i]初始化为0，第V次d[i]是否仍存在更新。复杂度为O(EV)。
3. Dijkstra算法（单源最短路）：从起点出发<s, d[s]=0>出发，更新s所有可到达的边j，若d[j]有更新，则加入最小堆，以便下次找到剩余集合中d[i]最小的点i，再从i出发BFS，直到到达终点t。不能处理包含负权边的图。复杂度为O(ElogV)。
4. Floyd-Warshall算法（多源最短路）：定义从i到j且经过k的最短路为d[i][j]用d[i][k]+d[k][j]来更新，三重循环直接得到任意两点间的最短路。图可包含负权边，包含负环的判断方法为是否存在顶点i使d[i][i]为负。复杂度O(V^3)。
5. Prim算法（最小生成树）：假设V的子集X已经构造了部分最小生成树，那么接下来就是选取从X到X的补集中权值最小的边加入。可使用最小堆维护待选的边，复杂度为O(ElogV)。
6. Kruskal算法（最小生成树）：将所有边升序排列，依次取出每条最小的边，若该边的两个端点不在相同并查集内，则将该边加入最小生成树，并将两点用并查集连接。耗时最多的操作为边的排序，复杂度O(ElogE)。

2.5.2 优化细节

1. 最短路本质是动态规划，最小生成树本质是贪心。
2. Bellman-Ford算法和Floyd-Warshall算法可处理包含负权边的图，并结合各自特性判断是否存在负环。
3. 差分约束：将不等式组转化为包含负权边的单源最短路问题，一般采用Bellman-Ford方法解决。若d[i]+x>=d[j]，则创建有向边e(i,j)=x。从起点s到终点t的最短路d[t]为s和t允许的最大差。若存在负环，则不等式组无解；若d[t]=INF，则s和t相差可任意。

2.6 数论

2.6.1 核心思想

1. 辗转相除算法（最小公约数）：gcd(a,b)=gcd(b,a%b)，循环至b为0，此时得到最小公约数为a。
2. 扩展欧几里德算法（解二元一次方程）：求解ax+by=gcd(a,b)，类似辗转相除法。求extgcd(a,b,&x,&y)时，递归求得d=extgcd(b,a%b,y,x)的解存入y和x。则ax+by=gcd(a,b)的解为x和y-(a/b)*x。
3. 素数筛法：通过已求得的素数，将所求范围内所有该素数的倍数都标记为合数。依序遍历空间，未被筛掉的即为新的素数。复杂度O(nloglogn)，可看作线性的。
4. 反复平方法（快速幂）：求x的n次幂，可二分递归求x的n/2次幂，即x^n=(x^(n/2))^2 * x^(n&1)。复杂度为O(logn)。

2.6.2 优化细节

1. ax+by=gcd(a,b)的解大小：x的绝对值不大于b，y的绝对值不大于a。若要求得满足某个范围的解，可通过参数k调节，x+=k(b/d)、y-=k(a/d)为原方程的解簇。
2. 线性素数筛法：遍历解空间，无论当前数是否为素数，将已经求得得素数集合中的数乘以它得到合数标记筛去。并且若该数为合数，它乘以的素数为它的因子，则对该数不再继续循环已有的素数集合。上述可保证，每个合数都只通过乘以它最小的因子得到，即复杂度为线性。注意，该方法使得已有的素数集合中的组合并不一定被立即筛去，在以后遍历到特定合数时才会被标记。
3. 模运算：用64位处理对32数的模，避免发生溢出。模运算对加减乘可以直接应用，但对同模的两边做除法时，若原始ac=bc(mod m)，则a-b=m*k/c，则a=b(mod m/gcd(m,c))。

3.1 二分搜索

3.1.1 核心思想

1. 二分搜索：对于某个有序区间，每次查找区间中点是否满足条件，并以此为依据，决定递归查询左半区间或右半区间。反复循环上述折半过程，直到条件或精度被满足。

3.1.2 优化细节

1. STL：以函数lower_bound()和up_bound()的形式实现了二分搜索
2. 结束判定：1次循环可将区间减半，循环100次可达到精度10^-30 。还可通过区间长度与EPS判断，但要避免EPS太小因浮点数精度问题造成的死循环。

3.1.3 经典模型

1. 有序数组中查找某值
2. 判断一个假定解是否可行
3. 最大化最小值
4. 最大化平均值

3.2 常用技巧

3.2.1 核心思想

1. 尺取法：又称两点法，通过在区间上标记并顺序移动头尾两点，将复杂度降为线性。
2. 反转（开关问题）：若为初末态确定，则可通过贪心求得最少步骤。高斯消元法也可求得一组可行解，且自由变元有限，所以也可以求得最优解。
3. 集合的整数表示：通过二进制将集合状态映射至整数。涉及到的位运算包括：与、或、非（取反）、异或、取负（取反+1）、逻辑左移右移、交、并。遍历所有子集或找到所有大小为k的子集，都可以通过位运算操作求得字典序升序的二进制码。
4. 折半枚举（双向搜索）：当全局枚举复杂度太大时，可将条目折半，分别枚举所有情况。复杂度降为原本平方根。
5. 坐标离散化：将数列排序并去重，将原数列离散化映射至有限可控的区间。

3.3 数据结构（二）

3.3.1 核心思想

1. 线段树：是一棵完美二叉树，树上的每个节点表示一个区间。根节点维护整个区间，其他每个节点维护父节点二分后的某个区间。查询和更新复杂度都是O(logn)。
2. 树状数组（BIT）：将线段树每个节点的右儿子去掉，用每个节点表示区间的右边界代表该节点的索引，这样就可以通过一个线性数组维护所有必要的区间。索引的二进制最低位的1表示区间长度，值为x&-x。求和和更新复杂度都是O(logn)。
3. 平方分割：将n个元素装入√n个桶内，每个桶√n个元素的分桶法，每个桶分别维护自己内部的信息。对区间的复杂度操作可降至O(√n)。

3.3.2 优化细节

1. 懒惰标记：线段树可以通过在父节点上维护一个懒惰标记，来表示整棵子树的状态。在自顶向下的查询操作中，在递归该父节点时，将标记下移至两个儿子节点，并且更新父节点真正维护的直接变量。
2. 稀疏表：与线段树类似的是其区间长度都是2的整数次幂，但每个长度层级的区间左端点都连续。进行RMQ查询时，只需要找到不大于区间的最大2的整数幂，根据这个长度，待求解的左端点及右端点减去长度即为该行在稀疏表内的列的值。预处理时时间和空间复杂度都高达O(nlogn)，但结合二分查找的单次查询比线段树快，只需要O(loglogn)。
3. 维护多项式：如果需要维护的变量可以表示为索引i的n次多项式，则可以用n+1个树状数组来维护。或者，线段树的每个节点维护n+1个值。
4. 区域树：线段树的每个节点可以维护一个数组或维护一棵线段树，适合对矩形的区域进行处理。并且，和树状数组一样，多重线段树嵌套可以实现高维度的区域树。

3.4 动态规划（二）

3.4.1 核心思想

1. 状态压缩DP：通常结合进制数的特点，将每个状态压缩表示为整数。复杂特殊状态的转移就可以表示为整数下标的等式。
2. 矩阵快速幂：若动态规划的递推关系式可以表示为多元一次多项式，则可以通过某常系数矩阵的幂与初始向量的乘积求得最后的结果向量。其中求幂可以结合基于二分思想的快速幂算法。用n表示幂次数，m表示向量规模，则复杂度为O(m^3logn)。

3.4.2 优化细节

1. 结合数据结构：某些时候涉及到更新和查询操作时，如果利用线段树等高级数据结构处理，可以使得转移方程中线性的遍历转化为对数级别的查询。

3.5 网络流

3.5.1 核心思想

1. 最大流：增加反向补偿边，在残流网络上不断寻找增广路。常用朴素寻找增广路的Ford-Fulkerson算法，复杂度为O(FE)。通过最短路算法预处理为分层图的Dinic算法，复杂度为O(EV^2)。
2. 最小割：将割中的边全部删去后，源点无通路可再到达汇点。最小割是最大流的强对偶问题，数值相等。
3. 二分图匹配：匈牙利算法递归每个顶点，每次递归，将已有匹配删除看能否得到更优解。
4. 一般图匹配：常用Edmonds算法，较为复杂，尽量转化为二分图求解。
5. 最小费用流：在残流网络上扩展最短增广路时，使用边的花费作为边权寻找最短路。f(e)表示e中的流量，h(v)表示势（残流网络中s到v的最短路），d(e)表示考虑势后e的长度。复杂度为O(FElogV)或O(FV^2)。或者通过不断消去负圈得到最小费用流。

3.5.2 优化细节

1. 最大流变体：
   • 多个源点汇点：构造超级源点S和汇点T，用S连至多个源点，所有汇点连至T。
   • 无向图：构造正反方向的两条边，容量与无向边相同。
   • 顶点也有流量限制：将每点拆为入点和出点，入点至出点连边。
   • 最小流量限制：构造超级源S汇T，对于每条边构造逆向的容量为下限的满流圈；连接S到s及t到T之前，通过满流判断可行解。
   • 部分边容量发生变化：若影响原流，则设法将残流网络中对应边的容量减少或通过构造逆向圈等价减少。
   • 容量为负数：求最小割时可能出现负边，此时应通过数值变换设法消除负边。
2. 最小费变体：
   • 类最大流变体：构造方式相似。
   • 最小流量限制：将原边容量减少下限，构造新边容量为下限且费用为原费用减去一个足够大的数。
   • 流量任意：由于点的势会不断增加，所以仅在势为负数时增广，即能保证费用不断减小。
   • 费用为负：不能用Dijkstra算法，要用Bellmen-Ford算法处理负权边。另外，可以通过对所有边的费用和最终结果进行适当的变形避免负权边。
   • 最小化有流边的费用之和：无法通过最小费用流模型求解，需要建其他模。
3. 匹配相关对偶问题：
   • 连通图中，最大匹配+最小边覆盖=顶点数
   • 最大独立集+最小顶点覆盖=顶点数
   • 二分图中，最大匹配=最小顶点覆盖

3.6 计算几何

3.6.1 核心思想

1. 平面扫描：扫描线在平面上按既定轨迹移动时，不断根据扫描线扫过的部分更新，从而得到整体所求结果。扫描的方法，可以从左向右平移与y轴平行的直线，也可以固定射线的端点逆时针旋转。
2. 凸包：包围原点集的最小凸多边形的点组成的集合，称为原点集的凸包。凸包上的点不被原点集任意三点连成的三角形包含在内部。通过Graham扫描算法，将点集按坐标排序后，分为上下两条链求解。每次末尾加入新顶点，如果出现了凹的部分，则把凹点删去。Graham可以在O(nlogn)的时间内构造凸包。最远点对一定是凸包上的对踵点，可以通过旋转卡壳法不断找寻对踵点，在O(n)复杂度内求解。
3. 数值积分：通常在复杂的几何相交或求和问题中，通过对某个方向变量的微分，将立体切片或将平面切成线段后积分得到结果。

3.6.2 优化细节

1. 向量表示：可以使用STL的complex类表示向量，并进行相应的内积外积操作。
2. 计算误差：计算几何中的浮点数大小比较采取与ESP结合的方式，如a<0等价于a<-ESP，a≤0等价于a<ESP。由于double类型的精确尾数大约是10进制下的15位，当ESP太小时，可能造成假阴性。C++中可以采用更高精度的long double，Java可以使用BigDecimal。
3. 极限情况：当可行解可以取连续一段值时，很多时候只要考虑边界的极限情况。

4.1 数论（二）

4.1.1 核心思想

1. 线性方程组：可以采用高斯消元法求解。将方程组用矩阵表示后，遍历每列，保留该列系数最大的行（列主元高斯消元，减少误差），并将其乘以一定倍数用于消除其他行的该列元素。
2. 一次同余方程：ax=b (mod m)。定义a的逆元为y满足ay=1 (mod m)，则x=yb(mod m)。逆元y可以用扩展欧几里得求解。
3. 费马小定律：若p为素数，a与p互素，则有a^(p-1)=1 (mod p)。
4. 欧拉定理：对于一个正整数N的素数幂分解N=P1^q1P2^q2...Pn^qn，欧拉函数φ(N)=N(1-1/P1)(1-1/P2)...*(1-1/Pn)，意义是不大于N且与N互素的正数个数。此时，对于与N互素的x，有x^φ(N)=1 (mod N)。费马小定律可以看作欧拉定理的推广。
5. 线性同余方程组：若有解则一定有无数解，解的全集可写作x=b (mod m)。初始化为x=0，m=1。逐次加入一个新的方程ax=b (mod m)，将上一步的x用mt+b的形式代入，转化为一次同余方程。
6. 中国剩余定理：n=ab（a、b互素），则（x mod n）等价于（x mod a，x mod b）。所以，通过对n的质因数分解，可以通过只考虑模n的素因子的幂p^k来计算。
7. n!模p：将阶乘表示为n!=ap^e，则e=n/p+n/p^2+n/p^3+…。由于阶乘中不能被p整除的项呈现周期性，乘积为(p-1)!^(n/p)*(n mod p)!。根据威尔逊定理，(p-1)!=-1(mod p)。考虑可以被p整除的部分，通过全部除以p，可以递归到n/p的范围考虑。
8. 组合数模p：将n和m用p进制法表示后，根据Lucas定理，Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p) ，则对于每一位，计算其组合数模p，将答案相乘即为C(n, m)模p。
9. 容斥原理：先不考虑重叠的情况，将所有对象计算出来，再不断递归把重复计算的数目排斥出去，直到结果既无遗漏又无重复。由于递归时排斥采取减法，从全局来看应根据地柜深度的奇偶性判断符号正负。
10. 莫比乌斯函数：在容斥定理中，每次排斥的规模d如果是n的约数，则被加减多次的总和只和n/d有关。求这个系数的函数叫莫比乌斯函数，记作μ(n/d)。若x可以被大于1的完全平方数整除，则μ(x)=0；否则计算x的质因子个数k，μ(x)=(-1)^k。莫比乌斯反演定理利用μ(x)推出，f(n)=∑g(d)等价于g(d)=∑μ(n/d)*f(d)。
11. Polya计数定理：在组合问题中，有时要求把旋转和翻转之后的状态看作相同态，计算本质不同的个数。此时应把所有方案重复计算相同次数，再把结果除以重复的次数。另外，立方体的染色、相同颜色的数量限制、相邻状态限制，都可以用Polya求解。

4.2 博弈论

4.2.1 核心思想

1. 必胜策略：任意方式都无法转移到必胜态的为必败态N，存在一种方式可以转移到必败态的为必胜态P。
2. Nim：初始有n堆石子，每堆有ai石子，游戏规则是每次从某堆中取走至少一颗，判断初始状态是否必胜。若ai数组异或结果非0则为必胜态，否则为必败态。
3. Grundy数：当前状态的Grundy值是除任意一步所能转移到的状态的Grundy值以外的最小非负整数。所以，从Grundy为x出发，可以转移到Grundy为0到x-1的状态。Grundy数等价于Nim中的石子个数，再通过异或判断状态必胜与否。

4.2.2 优化细节

1. 取放石子：Grundy数可以转移到更大值，等价于Nim中放回石子。但可以通过采取对应策略再转移到原值的状态，所以对胜负没有影响。但此时，状态可能出现循环，所以需要注意可能会出现不分胜负、达成平局、永不结束的情况。
2. 复合游戏：由于在Nim中，只要异或值相同，石子堆数不影响局面性质。所以对分割后的各部分取异或，就可以用一个Grundy数来表示几个游戏复合而成的状态。

4.3 图论（二）

4.3.1 核心思想

1. 强连通分量：图中任意两点可互达的子图叫做强连通分量。任意有向图都可以分解为若干个不相交的强连通分量。将图中的强连通分量都缩成一个顶点，可以将原图转化为DAG（有项无环图）。
2. 强连通分量分解：通过两次DFS实现。第一次DFS时，回溯时为顶点标号（后序遍历）。标号越小表示离图尾越近，即搜索树的叶子。第二次DFS时，将所有边反向后，从标号大的顶点开始遍历，每次遍历的顶点集合组成一个强连通分量，记录该分量的拓扑序。接着，再取未访问节点中最大标号的顶点开始DFS，拓扑序加一。直到顶点全部遍历，算法结束。总的复杂度是O(V+E)。
3. 2-SAT：对于每个子句中文字个数不超过二的合取范式，可以将每个子句等价转化为两个蕴含关系，将所有蕴含关系为边、每个变量取真取假为点，构建有向图。图中的每个强连通分量内，若某个点为正确，则分量中所有顶点都为真。对于每个布尔变量，考虑其取真取假的两个点，点所在的强连通分量拓扑序大的点情况为真。由此，得到一组合法的布尔变量赋值。
4. LCA（最近公共祖先）：有根树中，两个结点的公共祖先中距离最近的那个成为LCA。高效求解LCA可以采用倍增法预处理加二分搜索，或中序遍历后利用线段树或BIT做RMQ求解。

4.4 常用技巧（二）

4.4.1 核心思想

1. 栈的应用：在栈内维护一个下标和对应值都单向递增的序列，则可求距离自己最近的比自己大的值。
2. 双向队列的应用：队列中维护一个以某区间内最小值开始，单向递增的序列，则可求窗口大小一定的滑动最小值。
3. 倍增法：通过预处理，计算出距离每个点2的次幂处的状态。由于转移到的目的地满足一定条件，且具有与下标单向相关性，所以可以通过二分搜索，每次将2的幂减1，判断是否出终极目标的位置。

4.4.2 优化细节

1. 数量的二进制表示：在一定数量的物品中挑选若干个，可以通过每次是否添加2的次幂个物品来决定最终结果。将原本枚举的复杂度O(n)降至二进制位数O(logn)。
2. 连续状态转移：在DP中，如果某状态可由连续的下标的一些状态转移来，并要求其最值。可以试着把状态转移方程分为两部分，一部分为常量，另一部分为只与前一状态下标有关。则问题转化为，求某个函数在某个滑动窗口内的最值。如果窗口大小固定不变，则可利用双向队列求解滑动最值。

4.5 智慧搜索

4.5.1 核心思想

1. 剪枝：调整搜索顺序，从分支少或影响大的部分开始搜索。无任何效用或无法到达最终态的步骤可以提前剪枝。没有最优解则剪枝，通常可以通过贪心等算法求得最优解下界的下界。
2. IDA：通过搜索判断是否有某个不超过x的解，将x从0开始每次加1，首次求到解的x就是最优解。这样，在搜索过程中，就不会访问比最优解更大的状态。迭代加深搜索（IDDFS）类似于宽度有限搜索，按距离初始状态的远近访问各个状态，而IDA会通过估算下届提前剪枝优化。
3. A*：BFS和Dijkstra利用下界优化，将优先队列中的键值改为初始状态到当前状态的距离加上到目标状态的距离下界。此时，优先队列顶端元素未必是初始状态到当前状态的最短路。

4.5.2 优化细节

1. IDA与A对比：
   • IDA针对DFS，A针对BFS。
   • IDA不怎么花费内存，A需要关于搜索空间的线性的内存。
   • 通过不同路径到达同一状态，IDA效率急剧下降，而A可以通过选取合适的下届保证每个状态至多检查一次。
   • IDA*在不断增加递归深度限制时重复搜索了很多状态，但总的访问状态数和最后一次访问状态数是同一数量级的。

4.6 分治

4.6.1 核心思想

1. 分治：将问题划分为更小规模的子问题，递归解决子问题，再将结果合并从而高效解决问题。
2. 数列上的分治：每次递归数列长度减半，合并时除将子问题的情况合并外，还需要考虑左右两个子数列交互问题。通常需要在递归时，维护数列状态，如排序或某些统计值大小。
3. 树上的分治：树的重心是指删除该顶点后最大子树顶点数最小的点。通过树的重心来分解树，可以避免分解不均匀导致的退化现象。按重心分割，可以保证，每次划分后子树的大小都不超过n/2，所以递归深度不超过O(logn)。
4. 平面上的分治：将待求解平面按x或y坐标分为两部分，各子问题递归求解，再合并。对于两子平面交互的部分，通常可以通过一些限制条件，只考虑有可能达到最优解的一些状态，可以极大降低复杂度。

4.6.2 优化细节

1. 树的递归：递归分解无根树时，可以代入两个参数，当前节点及父节点。在更新当前节点时，其所有相连顶点中，除去父节点及已被分解出去的子树根节点，其余就是可以继续递归的子节点。

4.7 字符串

4.7.1 核心思想

1. KMP：通过DP计算next数组，next[i]表示以模式串的第i个字符结尾的后缀与模式串前缀的最长公共子串中，公共子串结尾的位置。当模式串与母串进行匹配时，若发生字符不匹配的情况，可以将母串指针位置保持不变，将模式串的指针前移至next位置的后一个字符，若依然不等，递归next直到相等或者超出模式串头。复杂度O(m+n)。
2. Trie：树上的边对应字符，从根到节点的路径上的字符序列即为该节点表示的字符串。Trie是一个高效维护字符串集合的数据结构，查找长度为l的字符串复杂度为O(l)，同时节约空间。
3. AC自动机：又叫Aho-Corasick算法，将多个模式串的所有前缀用Trie表示，再在Trie上进行KMP。
4. Robin-Carp哈希：将字符串看作b进制数，循环移动头尾，可以得到每个串的哈希结果，用来判断两字符串是否匹配。可推广到二维情况的哈希算法。
5. 后缀数组（SA）：将字符串的所有后缀按字典序排列后得到的数组，sa[i]表示排名第i的后缀的起始位置，rank[i]表示其实位置为i的后缀的排名。利用倍增的思想，可以在log(n(logn)^2)时间内得到后缀数组。通过计算得到的长度为k的所有后缀及其排名，利用rank[i]和rank[i+2]组合得到长度为2k的后缀及排名。
6. 高度数组（LCP）：后缀数组中两个相邻后缀的最长公共前缀。由于h[i-1]≥h[i]-1，可以从左到右遍历后缀头的位置，通过尺取法，在O(n)时间内求得。由于高度数组的传递性，结合RMQ，可以求得任意两个后缀间的最长前缀。

4.7.2 经典模型

1. 串的状态转移：KMP／AC自动机
2. 单字符串匹配：KMP／Robin-Carp哈希
3. 多字符串匹配：Robin-Carp哈希／AC自动机／SA+二分搜索／扩展KMP
4. 最长公共子串：strcat+SA+LCP+RMQ
5. 最长回文子串：strcat+SA+LCP+RMQ／Manacher

面试高级算法梳理笔记