影响程序员发展的十类算法（zz）

字数统计: 5,990
  1. 基本思想（时空复杂度，规约，枚举，贪心，分治，递推与递归，构造，模拟）
  2. 排序（冒泡，选择，插入，归并，堆，快速，桶，基数，希尔，Timsort）（Top K）
  3. 经典数据结构（栈，队列，链表，哈希，单调队列，优先队列，平衡树，线段树，并查集）
  4. 搜索（BFS，DFS，A*搜索)
  5. 基础数学算法（二分查找算法，欧几里得算法，快速幂算法）
  6. 图论基础算法（拓扑排序，最小生成树算法，最短路径算法）
  7. 动态规划算法（最长上升子序列，最长公共子序列，最大连续子段和，背包问题）
  8. 计算几何算法（线段交，凸包，平面最近点对）
  9. 字符串匹配算法（KMP算法，Trie树）
  10. 网络流算法（最大流算法，最小费用最大流算法）

基本思想

时空复杂度

归约

问题：如果某个问题已经找到了一种解法，如何证明这个问题可解决的时间下界。
解法：用归约，从已知证未知。
enter image description here
A问题可以线性归约到B问题的转化是单向的，是从已知问题到未知问题，从难度更低的问题转化为难度更高的问题。如：一元一次方程可以归约到一元二次方程。
题目：使用排序算法对求凸包下界进行评估：
Sorting reduct to 2dCH

枚举

贪心

分治

Divide_and_Conquer

递推与递归

题目：求第$n$个斐波那契数
$$ f(n)=f(n-1)+f(n-2), f(1)=1, f(2)=1 $$

构造

题目：各阶幻方的构造算法

模拟

题目：给定麻将规则，问至少还需几轮能够胡牌

排序

  • 冒泡排序
  • 选择排序
  • 插入排序
  • 归并排序
  • 堆排序
  • 快速排序
  • 桶排序：将数组分到有限数量的桶里，每个桶再个别排序。题目：小学生成绩排名
  • 基数排序：将整数按位数切割成不同的数字，然后按每个位数分别比较。可以看做是从低位到高位进行的桶排序。
  • 希尔排序：也称递减增量排序算法，是插入排序的一种更高效的改进版本。
  • Timsort：一种混合的稳定的排序算法，派生自归并排序和插入排序。
    • Pyhton自从2.3版以来一直采用Timsort算法排序，Java SE7，Android，GNU Octave也采用Timsort算法对数组排序。

Sorting_algorithm_Timsort

题目：从$n$个数中找到前$k$大的数

经典数据结构

栈

队列

链表

哈希

题目：存在一个系数和变量都是整数的等式:
$$ a_1 x_1^3 + a_2 x_2^3 + a_3 x_3^3 + a_4 x_4^3 + a_5 x_5^3 = 0 $$
$\forall i∈{1,2,3,4,5}, x_i∈[-50,50], a_i∈[-50,50]$，问有多少组解。
解法：将变量分成两部分，先hash一部分的结果，另一部分计算出结果再去查找。

单调队列

题目：长度为$n$的数组上有个长度为$k$的滑窗从左向右移动，求每次移动后滑窗区间的最小值和最大值。输出两行，第一行所有最小值，第二行所有最大值。

monotone-queue-notes

解法：可以用线段树来做，复杂度O(nlogn)，但是使用单调队列更简单，复杂度是O(n)。

优先队列

堆的核心操作函数，维护堆:

Priority_Queue

BUILD: O(n), for (i=n/2; i>0; i–) max_heap(i);
UPDATE: O(logn)
INSERT: 先插入到堆的最后一个元素，然后不断和其父亲(/2)比较大小，一个for循环维护堆
DELETE: O(logn) 删除堆顶元素，把最后一个元素拿到堆顶，然后维护堆

平衡树

AVL

一种典型适度平衡的二叉搜索树。
需要为其中的每一个节点引入一个名为平衡因子的指标，节点的平衡因子是它的左子树的高度减去它的右子树的高度。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。

高度为$h$的AVL树，至少包含$S(h)=fib(h+3)-1$个节点

INSERT: O(1)
DELETE: O(logn)
优点: 无论查找、插入或删除，最坏情况下的复杂度均为O(logn)时间复杂度,O(n)的存储空间。
缺点:

  • 借助高度或平衡因子，为此需改造元素结构，或额外封装；
  • 实测复杂度与理论值尚有差距；
  • 单次动态调整后，全数拓扑结构的变化量可能高达O(logn) 。

RB-Tree（红黑树，即是B-树(2,4)）

引入“颜色”的目的在于使得红黑树的平衡条件得以简化，与B树对应。
INSERT: O(logn)
DELETE: O(logn)
优点:

  • 任何一次动态操作引发的结构变化量不超过O(1)，特别适合用来实现持久化的搜索树，作为可持久化数据结构比较好；
  • 红黑树每个节点只需要1-bit附加空间。

缺点:

  • 太复杂，插入有5种情况，删除有6种情况，代码量大，编写容易出错。
  • 红黑树并不是真正的平衡二叉树，但在实际应用中，红黑树的统计性能要高于平衡二叉树，但极端性能略差。

Splay

节点$V$一旦被访问，随即转移至树根，“一步一步往上爬”。
效率取决于：树的初始形态以及节点访问次序。可以做到单趟伸展操作，分摊O(logn)时间！
INSERT:O(logn)
DELETE:O(logn)
优点:

  • 无需记录节点高度或平衡因子；
  • 编程实现简单易行–优于AVL树，分摊复杂度O(logn)。
  • 局部性强、缓存命中率极高时，效率更好。

缺点: 仍不能杜绝单次最坏情况的出现，不适用于对效率敏感的场合。

线段树

也叫区间树，是一棵二叉树，适用于和区间统计有关的问题。

Segment_Tree

经典的问题模型：

  • 单点修改，区间查询
  • 区间修改，单点查询
  • 区间修改，区间查询

题目：给定原始数组$a[]={2,5,3,4,1}, a[i] <= n$，求$b[i]$=位置$i$左边小于等于$a[i]$的数的个数。如样例中$b[]={0,1,1,2,0}$。

解法：初始化线段树$1..n$位置上的数都为$0$，然后从左到右遍历数组，对于每个位置的数$a[i]$，$b[i]=sum(1, a[i]-1)$，然后在$a[i]$值所在的位置增加1。

并查集

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。
经典应用：Kruskal算法求最小生成树中判断新加入的边是否在同一棵树内部。

union_find_set

搜索

BFS

DFS

A*搜索

In the standard terminology used when talking about A, $g(n)$ represents the exact cost of the path from the starting point to any vertex $n$, and $h(n)$ represents the heuristic estimated cost from vertex $n$ to the goal.
A balances the two as it moves from the starting point to the goal. Each time through the main loop, it examines the vertex $n$ that has the lowest $f(n) = g(n) + h(n)$.
enter image description here
A*算法和DFS、BFS有着较深关系，其中的$g(n)$和$h(n)$作为两个不同的代价:

  1. 在DFS的搜索中，其关注的主要是邻居节点与当前节点的距离开销，此时可将$g(n)$认为是0；
  2. 在BFS中进行分层搜索时，以层次距离为主，此时可将$h(n)$认为是0。而且，当$h(n)$认为是0，则转换为单源最短路径计算。

题目：八数码问题

基础数学算法

二分查找算法

问题：在一个给定的升序数组array中，找到第一个大于或者等于x的数的位置，没有则返回-1。

int search(int[] array, int low, int high, int x) {
  int ans = -1;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (judge(mid)) {
      ans = mid;
      high = mid - 1;
    } else low = mid + 1;
  }
  return ans;
}

问题变形：

  • 求第一个大于x的数的位置
  • 求最后一个小于x的数的位置
  • 求最后一个小于或者等于x的数的位置
  • 如果当前数组不是升序而是降序的话

题目：给定$n$个木棍，每个木棍有一个长度（精确到两位小数），需要把他们截成$k$个长度相同的小木棍，求小木棍的最大长度。

解答：把最大长度的小木棍的值作为二分变量，进行浮点数的二分。

题目：一条长为L（1~1,000,000,000）的河中，有$n$(1~50,000)块可垫脚的石头，
给出它们与起始点的距离$rock[i]$，移除其中的$m$块使得具有最小间距的相邻两块石头之间的距离最大。

解答：二分最终的结果，用上述整数二分的写法进行处理，每一次判断使用贪心策略，记录每次符合条件的策略，二分最后得到的就是最终的答案。

二分经典应用：求上（下）界的最小（大）值

欧几里得算法

求两个整数的最大公约数－－辗转相除法

int gcd(int a, int b) {
	if (a == 0) return b;
	return gcd(b, a % b);
}

快速幂算法

问题：$a, b$都是整数，如何快速求$a^b$

int fpow(int a, int b){
    int result = 1;
    for (; b; b >>= 1) {
	    if (b & 1) result = result * a;
	    a = a * a;
	｝
    return result;
}

题目：快速求第$n$个斐波那契数。

解法：
经典的矩阵快速幂，下面这个式子是成立的：enter image description here
不停地利用这个式子迭代右边的列向量，会得到下面的式子：enter image description here
这样，问题就转化为如何计算这个矩阵的$n$ 次方了。

图论基础算法

拓扑排序

在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。

DAG

最小生成树算法

Prim算法

最小边、权的数据结构 时间复杂度（总计）
邻接矩阵、搜索 $O(V^2)$
二叉堆（后文伪代码中使用的数据结构）、邻接表 $O((V + E) log(V)) = O(E log(V))$
斐波那契堆、邻接表 $O(E + V log(V))$

Kruskal算法

kruskal算法的基本思想（使用到了并查集）：

  1. 首先将$G$的$n$个顶点看成$n$个孤立的连通分支（$n$个孤立点）并将所有的边按权从小大排序。
  2. 按照边权值递增顺序，如果加入边后存在圈则这条边不加，直到形成连通图

时间复杂度：$\mathrm {O} (Elog_{2}E) E$为图中的边数

最短路径算法

Dijkstra算法

对于不含负权的有向图，这是目前已知的最快的单源最短路径算法。
不采用最小优先级队列，时间复杂度是 ${\displaystyle O(|V|^{2})} )$(其中 $\displaystyle |V|$为图的顶点个数)。
用邻接表+二叉堆或者斐波纳契堆用作优先队列来查找最小的顶点时，时间复杂度是$O(|E|+|V|\log |V|) $(其中$\displaystyle |E|$是边数)

Floyd-Warshall算法

任意两点间的最短路径的一种算法，可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题，同时也被用于计算有向图的传递闭包。
Floyd-Warshall算法的时间复杂度为 $\displaystyle O(N^{3})$，空间复杂度为 $\displaystyle O(N^{2})$。

Floyd_Warshall

核心思想是动态规划算法，其中$dist[i][j]$表示由点 $\displaystyle i$到点 $\displaystyle j$的代价，∞ 表示两点之间没有任何连接。

动态规划算法

数字三角形[IOI 1994]

题目：有一个数字三角形，从最顶层出发，每一步只能向左下或右下方向走。编程求从最顶层到最底层的一条路所经过位置上的数字之和的最大值。

DP1

动态规划核心思想：

  • 最优子结构：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。
  • 重叠子问题：子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存起来，当再次需要计算已经计算过的子问题时，从保存的记录中查看一下结果，从而获得较高的效率。

DP2

最长上升子序列

最长公共子序列

最大连续子段和

背包问题

  • 01背包
  • 完全背包
  • 多重背包
  • 混合三种背包
  • 二维费用背包
  • 分组背包

计算几何算法

向量性质

向量点积

向量的点积结果跟两个向量之间的角度有关
enter image description here
enter image description here

向量叉积

向量积可以被定义为：$a \times b = absin\theta$（在这里$θ$表示两向量之间的夹角(共起点的前提下)（$0° ≤ θ ≤ 180°$）

Cross_Product

向量积（叉积、外积）的坐标表达式

$c$的长度在数值上等于以$a$，$b$，夹角为$θ$组成的平行四边形的面积。

To-Left Test

问题：给定三个二维平面的点，$p,q,r$，问$\overrightarrow{pr}$向量是否在$\overrightarrow{pq}$向量的左侧

解答：使用叉乘，结果大于0时在左侧，等于0时共线，小于0时在右侧。

问题：如何判断一个点是否在一个三角形内部

解答：$InTriangle(p,q,r,k)$当且仅当
$$ToLeft(p,q,k) == ToLeft(q,r,k) == ToLeft(r,p,k)$$
问题：如何判断一个点是否在一个凸多边形内部

解答：看所有的ToLeft值是否都大于0
问题：求给定多边形的面积

解答：把多边形分成若干个三角形，按照逆时针依次求每个三角形的有向面积。对用 $\displaystyle (x_{1},y_{1}),(x_{2},y_{2}),\dots ,(x_{n},y_{n})$（按逆时针排列）描述的多边形，其面积为：
$$\displaystyle A={\frac {1}{2}}\left({\begin{vmatrix}x_{1}&y_{1}\x_{2}&y_{2}\end{vmatrix}}+{\begin{vmatrix}x_{2}&y_{2}\x_{3}&y_{3}\end{vmatrix}}+\dots +{\begin{vmatrix}x_{n}&y_{n}\x_{1}&y_{1}\end{vmatrix}}\right)$$

凸包

点集Q的凸包（convex hull）是指一个最小凸多面体，满足Q中的点或者在多面体边上或者在其内。

Convex_Hull

经典算法：

  • 增量式算法：逐次将点加入，然后检查之前的点是否在新的凸包上，时间复杂度为 $\displaystyle O(n^{2})$。
  • 包裹法（Jarvis步进法）。时间复杂度为 $\displaystyle O(kn)$，$k$表示输出的面的数量，$n$表示点集的个数，复杂度与输出凸包的面相关。
  • 葛立恒（Graham）扫描法，算法的整体时间复杂度是 $\displaystyle O(n\log {n})$，缺点是只能处理二维情况。enter image description here
  • 分治法：将点集$X$分成两个不相交子集。求得两者的凸包后，计算这两个凸包的凸包，该凸包就是$X$的凸包。时间复杂度是$\displaystyle O(n\log {n})$。

    解决三维凸包问题，主要有包裹法、分治法、随机增量算法、快速凸包算法。

平面最近点对

给定平面上$n$个点，找其中的一对点，使得在$n$个点的所有点对中，该点对的距离最小。
经典算法：

  • 分治法，时间复杂度O(nlogn)
  • 随机增量法，时间复杂度O(n)，且向高维扩展容易

字符串匹配算法

KMP算法

问题：在一个主文本字符串S内查找一个词W的出现位置。
思想：通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。
enter image description here
next[j]取决于模式串中T[0 ~ j-1]中前缀和后缀相等部分的长度，并且next[j]恰好等于这个最大长度；此外在j位匹配出错，刚好是从next[j]位开始重新匹配；next[j]在j-1处产生。

void getnxt(char *t,int *f){ //字符串长度至少为1，求nxt数组
	int i,j,len=strlen(t);
	f[0]=f[1]=0;
	for (i=1; i<len; i++){
		j=f[i];
		while (j && t[i]!=t[j]) j=f[j];
		f[i+1]= t[i]==t[j] ? j+1 : 0;
	}
}

int kmp(char *s,char *t,int *f){ //这里肯定是O(n+m)的
	int i,j,tem,n=strlen(s),m=strlen(t);
	getnxt(t,f);
	for (i=j=0; i<n; i++){
		while (j && s[i]!=t[j]) j=f[j];
		if (s[i]==t[j]) j++;
		if (j==m) return i-m+1;
		//if (j==m) num++,j=f[j]; //若统计有多少个
	}
	return -1;
}

时间复杂度分析：在kmp函数中，每一次while 循环$j$的值都会减小（至少为1），然而每一次j++都伴随一次i++，所以总的复杂度是O(n)。在getnxt函数中过程类似。

题目：找出第一个字符串在第二个字符串中出现次数。

题目：求既是前缀串儿又是后缀串儿的不同子串的长度，长度从小到大输出。

解答：next数组的性质是，该字符之前的字符串的最大相同前缀后缀。既然知道了最大的，即next[len]，递归一次next[ next[len] ]，就能求得更小的前缀。不断的递归把所有所有可能的长度找出来，然后递归输出即可。

题目：给出一个字符串，求出这个字符串最多能够由多少个子串首尾连接而成。比如“ababab”就是由3个“ab”相连而成，所以输出3，“abcdef”只能看作一个“abcdef”所以输出1。

解答：KMP中next数组的巧妙运用。在这里我们假设这个字符串的长度是len，那么如果len可以被len-next[len]整除的话，我们就可以说len-next[len]就是那个最短子串的长度。

Trie树

问题：给你100000个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，求第一次出现在第几个位置。
又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。
enter image description here
题目：设计一个算法可以自动列出以输入字符串为前缀的单词中最频繁查找的前10个单词。

注：类似google搜索框中输入要查找的单词，输入前缀google会自动列出同一前缀的所有查找单词中top 10的

解答：

  1. 节点上记录每个单词被查找的次数
  2. 对于给定的输入词，找到其在Trie中的位置，设为节点K
  3. 搜索以节点K为根的子树，用一个最小堆记录top10

Trie树＋KMP

问题：在输入的一串字符串中匹配有限组“字典”中的子串。
AC自动机算法算是比较简单直观的字符串匹配自动机，它其实就是在一颗Trie树上建一些失配指针，当失配时只要顺着失配指针走，就能避免一些重复的计算。算法均摊情况下具有近似于线性的时间复杂度。

Trie_Tree

应用：多模式串匹配问题。当一个字典串集合是已知的(例如一个计算机病毒库), 就可以以离线方式先将自动机求出并储存以供日后使用。

  • UNIX系统中的一个命令fgrep就是以AC自动机算法作为基础实现的。
  • nginx模块用于判断User-Agent（用户的浏览器信息）的核心算法就是AC自动机

网络流算法

最大流算法

在优化理论中,最大流问题涉及到在一个单源点、单汇点的网络流中找到一条最大的流。

Maximum_flow_problem

经典算法

核心是将一条边的单向残留容量的减少看做反向残留流量的增加，然后每次寻找增广路径（就是新的流量），直到无法找到增广路径为止。

残留网络

  • Edmonds–Karp算法：使用广度优先搜索寻找增广路径。
  • Dinic算法
  • SAP算法

题目：有N个牛，F个食物，D个饮料，每个牛喜欢一些食物和饮料，现在要给牛分发食物和饮料，当一个牛得到一个喜欢的食物和一个喜欢的饮料的时候，就说这个牛被满足了。求最多可以满足多少个牛。每个饮料和食物只能被分给一个牛，每个牛也只能拿到一个饮料和食物。

enter image description here
解法：一头牛贡献一单位的流量，所以把牛拆了，中间加一个1容量的边，然后起点到所有饮料连1容量边，饮料到喜欢自己的牛连1容量边，牛到他喜欢的食物连1容量的边，所有食物向终点连1容量的边。

题意：有N个农场，P条无向路连接。要从1到N不重复走一条路地走T次，求所经过的直接连接两个区域的道路中最长道路的最小值。

解法：源点向1连容量T的边。二分最小长度，长度超过mid的边容量为0，否则为1，用最大流判可行性。

最小费用最大流算法

最小费用最大流问题是经济学和管理学中的一类典型问题。
在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从A到B，如何选择路径、分配经过路径的流量，可以达到所用的费用最小的要求。
在实际中：$n$辆卡车要运送物品，从A地到B地。由于每条路段都有不同的路费要缴纳，每条路能容纳的车的数量有限制，如何分配卡车的出发路径可以达到费用最低，物品又能全部送到。

最小费用最大流与一般增广路的区别在于，每次寻找的增广路都是代价最小的路径。以代价为边的权重，求单源最短路径。

MinimumCostMaximums-tFlow

题目：给出一个无向图，求从1到N走两次的最短路，每条路不能重复走。

解法：S向1连容量2，费用0的边，N向T连容量2，费用0的边，节点间连容量1，费用为边权的边。一次费用流。

题目：给出一个n*n的矩阵,每一格有一个非负整数Aij,(Aij <= 1000)现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大

解法：$k$为１或者２时可以动态规划
enter image description here

$k$为２时：

  • 四维dp，$dp[x_1][y_1][x_2][y_2]$表示从起点（1，1）开始到点$（x_1，y_1）（x_2，y_2）$的最优路线
  • 三维dp，因为$x_1+y_1=x_2+y_2=k$(当前走的步数)，所以$dp[k][x_1][x_2]$表示走了$k$步第一个人停留在$x_1$位置，第二个人停留在$x_2$的位置（对应的$y$值可以算出来）。

解法：用最小费用最大流来解
对于每一个格子，我们拆成两个点（因为要限制流量）；每一个格子可以取一次，但是每一个格子是可以走多次的，那么我们在两个点中建两种边：

  1. 费用为权值，流量为１

  2. 费用为0，流量为$\infty$（或$k-1$, $k$都行）

    enter image description here