数据结构和算法相关整理

Posted on Edited on In

数据结构(Data Structure)

数据的基本单位是数据元素，最小单位是数据项。

数据与其组成方式即数据元素间的关系一同构成数据结构。数据结构在逻辑上的分类有集合、线性结构、树结构和图结构等。数据结构的选择取决于问题。

数据与其基本操作和处理方式一同构成抽象数据类型(ADT; Abstract Data Type)。

算法(Algorithm)

算法被定义为若按其执行可完成某一特定任务的有限指令集合。算法一词最早来源于波斯数学家花拉子米(Al-Khwarizmi)，在中国则最早见于「周髀算经」。算法的五个特征如下。

  • 输入(Input)：零个或多个输入；
  • 输出(Output)：一个或多个输出；
  • 确定性(Definiteness)：每一步骤对应的指令无二义性；
  • 有穷性(Finiteness)：有限的步骤，每一步骤在可接受的时间内完成；
  • 有效性(Effectiveness)：每一步骤都是可执行的。

程序可被定义为由编程语言表达的算法。

数据结构 + 算法 = 程序。 ——Niklaus Wirth

描述算法的方法有自然语言、程序设计语言、流程图和伪代码等。其中伪代码被称为算法语言。

算法验证(Algorithm Validation)的工作是证明算法对所有可能的合理输入都能计算出正确的结果。

调试只能指出错误的存在，而并不能指出其不存在。 ——Dijkstra

性能测量(Performance Measurement)又称分析(Profiling)，测量算法计算结果所需的时间和空间。

  • 时间复杂度(Time Complexity)：算法到运行结束时所需要的计算时间；
  • 空间复杂度(Space Complexity)：算法到运行结束时所需要的内存。

渐进符号(Asymptotic Notations)指问题规模趋近时，复杂度的数量级表示。

常用的渐进符号

常用的渐进符号如下表。

渐进符号 描述
上界与下界
上界
下界

程序步(Program Step)是程序中有明确语义的一个片段，其执行时间独立于实例特征(输入、参数等)。

时间复杂度可考虑如下三种情况。

  • 最好情况步数(Best-Case Step Count)；
  • 最坏情况步数(Worst-Case Step Count)：最经常分析的情况；
  • 平均步数(Average Step Count)。

为了对一个短的时间计时，往往需要重复多次，将总用时除以重复的次数。

阿克曼函数(Ackermann Function)的定义如下。

阿克曼函数增长得特别快。而阿克曼反函数则以非常慢的速度增加，通常使用表示，阿克曼反函数通常出现在时间复杂度分析中。

主定理(Master Theorem)可快速求得关于递归算法的复杂度。

线性表(Linear List)

线性表即有限序列，可分为如下两类。

  • 「顺序表」：即数组，逻辑顺序和存储顺序一致，一般仅存取、修改两种操作(本质上，存取和修改两种操作对应寻址这一种操作)；
  • 链表(Linked List)：逻辑顺序和存储顺序不一定一致。

单链表(Singly Linked List)只能访问结点后继。单链表设置头结点的目的是统一空表和非空表的情况，使得编程方便。单链表逆置的操作如下。

1
2
3
4
5
6
7
8
9
p = head->next;
pre = nullptr;
while(p != nullptr) {
    r = p->next;
    p->next = pre;
    pre = p;
    p = r;
}
head->next = pre;

双链表(Doubly Linked List)既能访问结点的前驱又能访问其后继，删除和插入操作方便。

单循环链表(Circular Singly Linked List)从表中任意结点出发都能扫描整个链表。单循环链表设置尾指针而非头指针，使查找终结点的时间为而非。以尾结点单循环链表为例，插入结点于表尾的操作如下。

1
2
3
s->next = rear->next;
rear->next = s;
rear = s; // 更新尾结点

删除头结点的操作如下。

1
2
3
q = rear->next->next;
rear->next->next = q->next;
delete q;

若经常性地删除最后一个结点，可考虑双循环链表(Circular Doubly Linked List)以节省运算开销。

可由一个尾指针唯一确定的链表有单/双循环链表和双向链表。

广义表(Generalized List)即允许表中有子表的情况。非空广义表可表示为如下形式。

通常，这些被称为原子(Atom)。上式广义表的表头和表尾定义如下。

  • 表头：；
  • 表尾：。

非空广义表的表尾总是一个广义表。广义表使得。

空表即，其表头、表尾均未定义。

递归表即。

广义表的存储结构如下。其中：tag区分原子和子表；hp指示连接本子表的元素；tp连接下一元素。无论方式Ⅰ还是方式Ⅱ都不破坏元素间并列的关系。

1
2
3
4
5
6
7
8
9
struct Node {
    int tag;
    union {
        char atom;
        struct {
            Node *hp, *tp;
        } ptr;
    }
};
1
2
3
4
5
6
7
8
struct Node {
    int tag;
    union {
        char atom;
        Node* hp;
    }
    Node* tp;
};

稀疏矩阵(Sparse Matrix)

稀疏矩阵的压缩存储方式有三元组顺序表和十字链表等，但这使必然失去随机存取功能。

稀疏矩阵不属于「特殊矩阵」。所谓「特殊矩阵」指有很多值相同的元素，且它们的分布很有规律。常见的「特殊矩阵」有对角矩阵、三角矩阵、对称矩阵等。

栈(Stack)

栈满足后进先出(LIFO; Last In First Out)规则，所有插入和删除操作都在栈的一端即栈顶(Top)进行。

栈和队列能出现的异常状况如下。

  • 上溢(Overflow)：缓冲区满但写入；
  • 下溢(Underflow)：缓冲区空但读出。

C++标准库提供了栈的实现std::stack(需要包含头文件<stack>)。注意stack::pop仅仅移除栈顶数据，而并不会返回之；若要访问栈顶数据需用stack::top。

卡特兰数(Catalan Number)

假设有足够大的栈，个元素以一定顺序入栈，出栈顺序的种数称为卡特兰数，定义如下。

出栈序列的判断技巧是，在输出序列中任意元素后面不能出现比该元素先入栈，且入栈顺序升序的两个元素。

逆波兰表示法(RPN; Reverse Polish Notation)

又称后缀表示法(Postfix Notation)，而常见的数学公式和程序设计语言表达式均为中缀表示法(Infix Notation)。举例而言，中缀表示法的a+b*c-d/e，可转换为逆波兰表示法的abc*+de/-。

中缀表示法转换为逆波兰表示法的规则如下。

  • 遇操作数则输出；
  • 遇括号时，若是(则压入堆栈，优先级降至最低；)则逐个弹出，并弃置(；
  • 遇运算符时，若优先级大于栈顶运算符则压入堆栈；优先级小于或等于栈顶运算符则弹出再比较；
  • 最后若堆栈中有剩余内容，则依次弹出。

逆波兰表示法的运算也借助堆栈。

队列(Queue)

一般而言，队列满足先进先出(FIFO; First In First Out)的规则，所有插入操作在一端即队尾(Rear)进行，而所有删除操作在另一端即队首(Front)进行。栈和队列的区别在于对插入和删除操作的限定不同。

下例计算队列的长度。

1
size_t size = (rear - front) % MAX_SIZE;

入队注意更新尾指针。

1
rear = (rear + 1) % MAX_SIZE;

C++标准库提供了队列的实现std::queue(需要包含头文件<queue>)。

循环队列(Circular Queue)

循环队列是队列的一种高效实现，其目的是为了克服「假溢出」的状况，循环队列区分空满状态的方法如下。

  • 浪费一个数组单元；
  • 引入标识变量；
  • 引入计数器。

优先队列(Priority Queue)

优先队列是任意支持查找、插入以及删除最值操作的数据结构，不满足先进先出的规则。

C++标准库提供了优先队列的实现std::priority_queue(需要包含头文件<queue>)。

下例重新定义std::priority_queue的比较规则。

1
2
3
4
5
class Compare {
    bool operator()(Node a, Node b) {
        return a.value() > b.value();
    }
};

使用自定义比较规则，则需要书写如下形式的声明。

1
priority_queue<Node, vector<Node>, Compare> q;

堆是优先队列的实现之一。

树(Tree)

树被定义为一个或多个结点的有穷集合，具有层次关系且不存在环路。存在一个特殊的称为根(Root)的结点，且除根节点外其余结点能被划分为棵不相交子树(Subtree)树的集合。

一个结点的子树的根被称为这个结点的子(Children)结点，这个结点被称为孩子的父(Parent)结点，同一父结点的子结点称为兄弟(Siblings)。一个结点的祖先(Ancestor)是指从根到该结点路径上的所有结点。

结点的度(Degree)即结点拥有的子树个数。有序树指结点各子树有序，不能互换。因此易知「度为2的树」与「二叉树」概念上并不相同。

度为0的结点称为叶(Leaf)结点或终止(Terminal)结点。

可以用二叉链表实现树，指针域分别指向该结点的「第一个子结点」和「右兄弟」。

二叉树(Binary Tree)

二叉树遍历的递归写法如下。

1
2
3
4
5
6
7
8
void visit(Node* root) {
    if(root == nullptr) return;
    // 先序(Pre Order)遍历操作
    visit(root->lchild);
    // 中序(In Order)遍历操作
    visit(root->rchild);
    // 后序(Post Order)遍历操作
}

先序、中序和后序遍历分别对应波兰表示、去括号的中缀表示和逆波兰表示。任意二叉树的叶子结点前序、中序和后序遍历中相对次序保持不变。

所有结点的子树斜偏向同一侧的二叉树称为斜二叉树(Skewed Binary Tree)。前序和后序相反的二叉树结点数即深度；前序和中序相同的为右斜树；中序和后序相同的为左斜树。

树的层序遍历即广度优先搜索，二叉树的顺序存储是按层序存储的。

个结点的二叉树共计种。一棵个结点的二叉树共计个指针域，个指向非空结点，个为空。

若高度为的二叉树没有度为1的结点，结点最小值为，最大值为(即满二叉树)。

考虑分枝数，可知，又由可得。

树与二叉树的对应关系

二叉树与普通树逻辑关系的对应如下表。由普通树转换为二叉树，根结点的右孩子总为空。

二叉树 树
左子结点 第一个子结点
右子结点 右兄弟

满二叉树(Full Binary Tree)

正好包含个结点的高度为的树。

个结点的满二叉树满足和(即)。

完全二叉树(Complete Binary Tree)

若层序遍历从1标号到，其结点对应一棵相同高度的满二叉树从1标号到的那些结点。

个结点的完全二叉树高度为，叶子数，编号最小的叶子序号是。

哈夫曼树(Huffman Tree)

即最优二叉树，保证带权路径长度(WPL; Weighted Path Length)最短。带权路径长度即，其中：表示第个叶子结点的权值；表示第个叶子结点至根节点的路径长度。

哈夫曼树的构造步骤如下。

  1. 棵二叉树森林；
  2. 选两棵权值最小的作为左右子树，新二叉树的权值为两子树权值之和。
  3. 删除上步骤选中的两棵子树，加入新生成的二叉树；
  4. 重复步骤2、3直至只剩一棵树。

根据哈夫曼树产生哈夫曼编码的代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
void huffmanCode(Node* root, vector<bool> curcode) {
    if(root->isLeaf()) {
        dic[root->value()] = curcode;
        return;
    }
    vector<bool> lcode = curcode;
    vector<bool> rcode = curcode;
    lcode.push_back(false);
    rcode.push_back(true);
    huffmanCode(root->lchild, lcode);
    huffmanCode(root->rchild, rcode);
}

哈夫曼树由个分支结点经过次合并而获得，没有度为1的结点。

线索二叉树(Threaded Binary Tree)

二叉树按某种次序遍历得到前驱和后继，其线索化即如下操作：若结点无左子树，则左指针指向其前驱结点；若结点无右子树，则右指针指向其后继结点。

通常设立某种标记，标记为真时结点被线索化，反之则指向子树。

二叉搜索树(Binary Search Tree)

又称「查找二叉树」或「排序二叉树」，递归地满足结点值大于任意左子树结点，小于任意右子树结点。有时，规定二叉搜索树中所有的值不允许出现重复。

二叉搜索树中，最值元素不一定是叶子结点。

任意结点的数值位于两子结点的数值之间的不一定是查找二叉树。

平衡二叉树(AVL Tree; Adelson-Velskii-Landis Tree)

定义平衡因子(BF; Balance Factor)如下。

的二叉树倾向左侧，的二叉树则倾向右侧。平衡二叉树递归地满足。

令、、和表示破坏平衡结点的插入方式，并视为不平衡的一种状态，如为在左子树根结点的左子树插入结点而破坏平衡。分别记左旋和右旋为「」和「」，通过如下的方式找到最小不平衡子树再旋转，是平衡二叉树的构建方式。

  • LR LL (平衡状态)；
  • RL RR (平衡状态)。

红黑树(Red Black Tree)

红黑树大致上是平衡的，称「非严格平衡」，具有如下性质。

  • 每个结点非红即黑；
  • 根结点为黑色；
  • 树尾的空项算为黑色；
  • 红结点的子结点必是黑色；
  • 任一路径含相同数目黑结点。

红黑树中没有一条路径会比其他路径长两倍。

若搜索次数远大于插入、删除的次数，选择AVL树；若搜索、插入和删除的次数差不多，则选择红黑树。

堆(Heap)

一个最大堆(Max Heap)是一棵完全二叉树，满足堆性质(Heap Property)即每个结点的值都至少与其孩子的值一样大。最大堆的定义意味着最大元素就在堆的树根。

在堆中插入一个元素，可以在堆的底部加入该元素，然后比较该元素与其祖先结点，直到它小于或等于其中的一个值，这个过程被称为Shift Up。

删除一个元素，则将要删除的元素位置清空，将堆末元素置入该位置，然后向下调整交换，将子结点中最大的元素交换上来，直至不能调整，这个过程称为Shift Down。一般情况下，删除的为根结点元素。

C++标准库的堆操作

C++标准库支持如下堆操作。其中，pop_heap()不移除容器中的元素。

操作 描述
is_heap(first, last) 判断是否为最大堆。
make_heap(first, last) 构造最大堆。
push_heap(first, last) 将last位置的元素添加至
[first, last)的最大堆中。
pop_heap(first, last) 将first和last的值交换，并令
[first, last)变为堆。
sort_heap(first, last) 将最大堆变为升序序列范围。

B树(B-Tree)

阶B树满足如下性质。

  • 每个结点最多个子结点；
  • 根、叶外结点之少个子结点；
  • 若根非叶，至少有两个子结点；
  • 所有叶在同一层；
  • 含个子结点的父节点有个关键码；
  • 关键码个数满足。

森林(Forest)

森林被定义为棵不相交的树的集合。

若个顶点条边的无向图是森林，则其必有棵树。

由森林向二叉树的转换如下。

  1. 将森林中每一棵树转为二叉树；
  2. 第一棵树的根视为根结点，将下一棵树接至根的右孩子；
  3. 重复步骤2。

并查集(DSU; Disjoint Set Union)

根结点的值始终为负数，其取相反数表示集合元素的个数；其他结点的值为与它处于同一集合的结点索引(在unite()操作后)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int dsu[MAX];
int find(int x) {
    if(dsu[x] < 0) return x;
    // 路径压缩优化，记录根结点再返回，以便后续的根结点查询
    return dsu[x] = find(dsu[x]);
}
bool equal(int x, int y) {
    return find(x) == find(y);
}
int count(int i) {
    return -dsu[find(i)];
}
void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x != y) { // 若不处于同一集合
        dsu[x] += dsu[y]; // 更新集合元素个数
        dsu[y] = x; // 绑定于根结点
    }
}

图论(Graph Theory)

欧拉使用图解决经典的哥尼斯堡桥问题(Königsberg Bridge Problem)，成为图论的创始人。

图(Graph)

图的顶点(Vertex)集有穷非空，边(Edge)集可空。

  • 无向图(Undirected Graph)：边的顶点对是无序的，至少0条边，至多条边；
  • 有向图(Directed Graph)：边是由有向对表示的，至少0条边，至多条边。

顶点的度(Degree)等于与它相接的边的条数。对于有向图，的入度(In Degree)是为头的所有边的数量，出度(Out Degree)是为尾的所有边的数量。

零图(Null Graph)即边集为空的图。

平凡图(Trivial Graph)顶点集大小为1的零图。

无向边使用表示，有向边使用表示。若有无向边边，则和的关系是相邻(Adjacent)，和、的关系是相接(Incident)；对于有向边，称为头(Head)，而称为尾(Tail)，相邻到(Adjacent to)，而由相邻(Adjacent from)。

悬挂点(Pendant Vertex)指只有一条边与之相接的点，所对应边则称为悬挂边(Pendant Edge)。

子图(Subgraph)指顶点集和边集分别是某一图顶点集的子集和边集的子集的图。路径(Path)是一个顶点的序列，其中是图中的边。简单路径(Simple Path)要求不能是重复的顶点。个顶点的图，简单路径长度不超过。

欧拉指出，从任意顶点出发存在一条通过所有的边恰好一次并返回出发地的路径，当且仅当「所有顶点的度数均为偶数」，而满足这样条件的路径被称为欧拉路径。

环(Cycle)是图中只有首末顶点重复的非空路径。没有环的图称作无环图(Acyclic Graph)，没有环的有向图称为有向无环图(DAG; Directed Acyclic Graph)。

存在到的路径，则这两点连通(Connected)。

树是连通无环图。

割点(Cut Vertex)是去掉后使图不再连通的点。所对应边则称为割边(Cut Edge)，又称桥(Bridge)。

无向图的一个连通分支(CC; Connected Component)就是最大的连通子图；有向图的任意一对顶点都存在路径，则此图强连通(Strongly Connected)，其连通分支称为强连通分支(SCC; Strongly CC)。个顶点的强连通图至少条边，形状为环状。

有向图的弱连通(Weakly Connected)指有向边换位无向边后可连通；有向图的单向连通(Singly Connected)指任意一对顶点至少一向可连通。强连通图必然单项连通，单项连通图必然弱连通。

简单图(Simple Graph)

平行边(Multiple Edges)指相接于同一对顶点的边。自环(Loop)指顶点与顶点自身连结的边。简单图指不含平行边和自环的图。

允许平行边的图称为多重图(Multigraph)，又译多图，或称伪图(Pseudograph)。一般情况下讨论的都是简单图。

多重图与超图(Hypergraph)不同，超图是指一条边可以连接任意数量的节点，而不只是两个。

完全图(Complete Graph)

每个顶点都与其余顶点相连的无向图。通常记阶完全图为。

若存在顶点集的划分使图中任一边端点分别在、中，称为二部图(Bipartite Graph)，又称二分图或偶图。通常记完全二部图为。

最小生成树(MST; Minimum Spanning Tree)

图的生成树的唯一性不能确定，个顶点图的生成树有条边。

Prim

Prim的伪代码
PRIM
输入：图；
输出：最小生成树。
从中任取顶点作为最小生成树的根，加入到中;

在连接内顶点与内顶点的边中选取权值最小的边作为MST的边;
将加入;

Prim的复杂度为。Prim实现的代码如下。

其中，graph是图的邻接矩阵形式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int prim(int (&graph)[N][N]) {
    int res = 0;
    bool visit[N] = {0};
    int lowcost[N] = {0};
    visit[0] = true;
    for(int i = 1; i <= N - 1; ++i) {
        lowcost[i] = graph[0][i];
    }
    for(int i = 1; i <= N - 1; ++i) {
        int min = INF;
        int p = -1;
        for(int j = 0; j < N; ++j) {
            if(!visit[j] && min > lowcost[j]) {
                min = lowcost[j];
                p = j;
            }
        }
        if(min == INF) return -1;
        res += min;
        visit[p] = true;
        for(int j = 0; j < N; ++j) {
            if(!visit[j] && lowcost[j] > graph[p][j]) {
                lowcost[j] = graph[p][j];
            }
        }
    }
    return res;
}

Kruskal

Kruskal的复杂度为。Kruskal实现的代码如下。

其中，graph是图的邻接表形式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
struct edge {
    int u;
    int v;
    int w;
    edge(int u_, int v_, int w_): u(u_), v(v_), w(w_) { }
};

int dsu[MAX];

int find(int x) {
    if(dsu[x] < 0) return x;
    return dsu[x] = find(dsu[x]);
}

int kruskal(vector<edge> graph) {
    memset(dsu, -1, sizeof(dsu));
    sort(graph.begin(), graph.end(), [](edge x, edge y) {
        return x.w < y.w;
    });
    int count = 0;
    int res = 0;
    for(size_t i = 0; i < graph.size(); ++i) {
        int u = graph[i].u;
        int v = graph[i].v;
        int w = graph[i].w;
        int t1 = find(u);
        int t2 = find(v);
        if(t1 != t2) {
            res += w;
            dsu[t1] = t2;
            count++;
        }
        if(count == N - 1) break;
    }
    if(count < N - 1) return -1;
    return res;
}

全源最短路径(All-Pairs Source Shortest Path)

Floyd-Warshall是全源最短路径的直接算法，其复杂度为，可以应用于包含负权值的图，但不可以判断是否存在负权回路。

Floyd-Warshall算法是一种动态规划的算法，最佳子结构为从顶点到顶点可经由前个顶点的最短路径，状态转移式如下。 实现的代码如下。

其中，graph是图的邻接矩阵形式。

1
2
3
4
5
6
7
void floyd_warshall(int (&graph)[N][N]) {
    for (int k = 0; k < N; ++k)
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                if (i != j && graph[i][j] > graph[i][k] + graph[k][j])
                    graph[i][j] = graph[i][k] + graph[k][j];
}

单源最短路径(Single Source Shortest Path)

艾兹赫尔·韦伯·戴克斯特拉(Edsger Wybe Dijkstra)

荷兰计算机科学家，是荷兰第一位以程序为专业的科学家。

Dijkstra

Dijkstra的伪代码
DIJKSTRA
输入：图，起点；
输出：由至其余各顶点的距离。
连接的各边 的权值;
将加入;

从中选出最小的顶点;
将加入;
与相邻且属于的所有顶点
的权值 的权值;

Dijkstra复杂度为，不可以应用于包含负权值的图。实现的代码如下。

其中：graph是图的邻接矩阵形式；dis存储从源出发到各结点的最短路径长度；path存储在这一最短路径中各节点的上一结点；src即源结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void dijkstra(int (&graph)[N][N], int (&dis)[N], int(&path)[N], int src) {
    bool visit[N] = {0};
    for (int i = 0; i < N; ++i) {
        dis[i] = graph[src][i];
        path[i] = ((graph[src][i] < INF) ? (-1) : (src));
    }
    for (int i = 0; i < N - 1; ++i) {
        int u = -1;
        int min = INF;
        for (int j = 0; j < N; ++j) {
            if (!visit[j] && dis[j] < min) {
                min = dis[j];
                u = j;
            }
        }
        if(u == -1) break;
        visit[u] = true;
        for (int j = 0; j < N; ++j) {
            if (j == src) continue;
            if (dis[j] > dis[u] + graph[u][j]) {
                dis[j] = dis[u] + graph[u][j];
                path[j] = u;
            }
        }
    }
}

使用「优先队列的堆优化」可将复杂度降至，实现的代码如下。

其中，graph是图的邻接表形式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
struct node {
    int u;
    int w;
    node(int u_ = 0, int w_ = 0): u(u_), w(w_) { }
    bool operator<(const node & other) const {
        return w > other.w;
	}
};

struct edge {
    int v;
    int w;
    edge(int v_ = 0, int w_ = 0): v(v_), w(w_) { }
};

void dijkstra(vector<edge> (&graph)[N], int (&dis)[N], int(&path)[N], int src) {
    bool visit[N] = {0};
    for(int i = 0; i < N; ++i) {
        dis[i] = INF;
        path[i] = -1;
    }
    for(size_t i = 0; i < graph[src].size(); ++i) {
        path[graph[src][i].v] = src;
    }
    dis[src] = 0;
    priority_queue<node> q;
    q.push(node(src, 0));
    while(!q.empty()) {
        node tmp = q.top();
        q.pop();
        int u = tmp.u;
        if(visit[u]) continue;
        visit[u] = true;
        for(size_t i = 0; i < graph[u].size(); ++i) {
            int v = graph[u][i].v;
            int w = graph[u][i].w;
            if(!visit[v] && dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                path[v] = u;
                q.push(node(v, dis[v]));
            }
        }
    }
}

Bellman-Ford

复杂度为，可以应用于包含负权值的图，也可以判断是否存在负权回路。实现的代码如下。

其中：graph是图的邻接表形式，返回值为true表示没有负环回路，为false表示存在负环回路，其他同前述。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct edge {
    int u;
    int v;
    int w;
    edge(int u_, int v_, int w_): u(u_), v(v_), w(w_) { }
};

bool bellman_ford(vector<edge> graph, int (&dis)[N], int (&path)[N], int src) {
    for(int i = 0; i < N; ++i) {
        dis[i] = INF;
        path[i] = -1;
    }
    dis[src] = 0;
    for(size_t i = 0; i < graph.size(); ++i) {
        if(graph[i].u == src) {
            path[graph[i].v] = src;
        }
    }
    for(int i = 1; i <= N - 1; ++i) {
        bool flag = false;
        for(size_t j = 0; j < graph.size(); ++j) {
            int u = graph[j].u;
            int v = graph[j].v;
            int w = graph[j].w;
            if(dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                path[v] = u;
                flag = true;
            }
        }
        if(!flag) return true;
    }
    for(size_t i = 0; i < graph.size(); ++i) {
        if(dis[graph[i].u] > dis[graph[i].v] + graph[i].w) {
            return false;
        }
    }
    return true;
}

搜索(Searching)

深度优先搜索的实现方式大致如下。

1
2
3
4
5
6
7
8
9
10
void dfs(int step) {
    if(...) { return; } // 剪枝或判断越界行为
    if(...) { ...; return; } // 判断终点、处理结果并返回
    for(...) {
        // 一些操作
        // 标记
        dfs(step + 1); // 进入下一层
        // 还原标记
    }
}

深度优先搜索常用剪枝(Pruning)操作，即跳过无论何种状态转移都不会存在的解。

广度优先搜索的实现方式大致如下。

1
2
3
4
5
6
7
8
9
10
11
12
void bfs(void) {
    queue<...> q;
    q.push(...); // 起始点入队
    while(!q.empty()) {
        auto p = q.front();
        q.pop();
        for(...) {
            // 一些操作
            if(...) q.push(...); // 满足下一步条件则入队
        }
    }
}

排列(Permutation; Arrangement)

将相异对象或符号根据确定的顺序重排，每个顺序都称作一个排列。

从个相异元素中取出个元素，排列数量的计算如下。 C++标准库提供了栈的实现std::next_permutation(需要包含头文件<algorithm>)，用于将个元素的不同排列生成出来，使用前需要保证个元素的序列是升序的，常见使用如下。

其中，std::next_permutation将在所有的排列生成后返回false。

1
2
3
4
sort(a, a + n);
do {
    ...
} while(next_permutation(a, a + n));

贪心(Greedy)

使用计算机模拟一个贪心的人做出决策的过程，即遵循某种规则，只考虑当前情况来选取最优策略。

动态规划(DP; Dynamic Programming)

规划(Programming)在数学上的意思，即寻找问题最佳化的一个过程。动态规划的关键思想如下：把大问题分成小问题，得到最佳子结构和状态转移式；将计算得到的相同问题的答案记录下来。

其他经典的动态规划问题

「切棍子」问题中，不同的棍子长度对应不同的价值，现切割长度为个单位的木棍，使其价值最大。「切棍子」问题的最佳子结构为在第个切割位置前的棍子的最大价值，状态转移式如下。 求解的代码如下。

1
2
3
4
5
6
for(int i = 1; i <= l; ++i) {
    for(int j = 1; j <= i; ++j) {
        if(dp[i-j] + value[j] > dp[i])
            dp[i] = dp[i-j] + value[j];
    }
}

「不相邻数字最大和」问题的最佳子结构为前个数字对此问题的最优解，状态转移式如下，注意设置递归出口和。

「带权区间调度」问题的最佳子结构为在任务之前所选任务的最高价值。令表示任务确定执行后，之前可选的最近的任务，「带权区间调度」问题的状态转移式如下。

「部分和」问题的最佳子结构为前个数字凑固定值的可能，状态转移式如下，注意出口、和的情况。

「多重部分和」问题的状态转移式如下。

最大连续元素和(MCS; Maximum Consecutive Sum)

最大连续元素和的解题思想为「如果在之前的最大和为负值，不如就从开始累加」。最佳子结构为在元素之前的最大连续元素和，状态转移式如下。

求解的代码如下。

1
2
3
4
5
int max = 0;
for(int i = 1; i <= n; ++i) {
    dp[i] = (dp[i-1] < 0) ? (value[i]) : (dp[i-1] + value[i]);
    if(dp[i] > max) max = dp[i];
}

分析得在的计算后可以舍弃，可将压缩为整型变量，更精简的代码如下。

1
2
3
4
5
6
int max = 0;
for(int i = 1; i <= n; ++i) {
    if(dp < 0) dp = 0;
    dp += value[i];
    if(dp > max) max = dp;
}

最长上升子序列(LIS; Longest Increasing Subsequence)

最佳子结构为之前序列的最长上升子序列数量，状态转移式如下。

求解的代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
int max = 0;
for(int i = 0; i < n; ++i) {
    dp[i] = 1; // LIS数量至少为1
}
for(int i = 1; i < n; ++i) {
    for(int j = 0; j < i; ++j) {
        if(value[j] < value[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
    }
    if(dp[i] > max) {
        max = dp[i];
    }
}

最长公共子串(LCS; Longest Common Subsequence)

令和分别表示两个字符串，状态转移式如下。

求解的代码如下。

1
2
3
4
5
6
7
8
9
10
for(int i = 1; i < n; ++i) {
    for(int j = 1; j < m; ++j) {
        if(s[i] == t[j]) {
            dp[i][j] = dp[i-1][j-1] + 1;
        }
        else {
            dp[i][j] = (dp[i-1][j] > dp[i][j-1]) ? dp[i-1][j] : dp[i][j-1];
        }
    }
}

0-1背包问题(0-1 Knapsack Problem)

有个重量和价值分别为、的物品，从这些物品中挑选总重量不超过的物品，使价值总和最大。

求解的代码如下。

1
2
3
4
5
6
7
8
9
10
for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= w; ++j) {
        if(j < weight[i]) { // 放不下
            dp[i][j] = dp[i-1][j];
        } else {
            dp[i][j] = max(dp[i-1][j], // 不选
                value[i] + dp[i-1][j-weight[i]]); // 选
        }
    }
}

完全背包问题(Unbounded Knapsack Problem)

有个重量和价值分别为、的物品，从这些物品中挑选总重量不超过的物品，每种物品可以挑选任意多件，使价值总和最大。

求解的代码如下。

1
2
3
4
5
6
7
8
9
10
for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= v; ++j) {
        if(j < volume[i]) { // 放不下
            dp[i][j] = dp[i-1][j];
        } else {
            dp[i][j] = max(dp[i-1][j], // 不选
                value[i] + dp[i][j-volume[i]]); // 选
        }
    }
}

数论(Number Theory)

因数(Divisor)又称约数，某个数的因数指能被某个数整除的数。通常用表示能整除，即是的因子，反之则。

素数(Prime Number)又称质数，指除了1和它自身，不再有其它因数。合数(Composite Number)指除了1和它自身，还有其它因数。1既不是质数，也不是合数。

简单的素性判断可以通过如下的试除法(Trial Division)实现。

1
2
3
4
5
bool isPrime(int n) {
    for(int i = 2; i * i < n; ++i)
        if(n % i == 0) return false;
    return true;
}

素因数分解(Prime Factorization)即任何一个正整数都可写为累积式，其中是一个素数，这种表示方法是唯一的。由素因数分解可得如下定理。

  • 因数个数定理(Number of Divisors)：因数个数为；
  • 因数和定理(Sum of Divisors)：因数和为。

最大公约数(GCD; Greatest Common Divisor)计算的代码如下。

1
2
3
LL gcd(LL a, LL b) {
    return (b > 0) ? (gcd(b, a % b)) : (a);
}

最小公倍数(LCM; Lowest Common Multiple)计算的代码如下。

1
2
3
LL lcm(LL a, LL b) {
    return a / gcd(a, b) * b;
}

阶乘(Factorial)计算的代码如下。

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;

int factorial(int n) {
    return (n == 0) ? (1) : (n * factorial(n - 1));
}

int main(void) {
    cout << factorial(5) << endl;
    return 0;
}

斐波那契序列(Fibonacci Sequence)计算的代码如下。

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;

int fibonacci(int n) {
    return (n == 1 || n == 2) ? (1) : (fibonacci(n - 1) + fibonacci(n - 2));
}

int main(void) {
    cout << fibonacci(6) << endl;
    return 0;
}

记斐波那契序列的第项为，斐波那契序列具有如下性质。

  • ；
  • ；
  • ；
  • ；
  • 。

筛法(Sieve Theory)

筛法是素性判断的基本方法。

埃拉托斯特尼筛法(Sieve of Eratosthenes)

简称埃氏筛，即从2开始，将每个素数的各个倍数标记为合数。

欧拉筛法(Sieve of Euler)

在埃氏筛的基础上，用且仅用最小质因子筛出合数，避免重复标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
bool isPrime[MAX];
std::vector<int> prime;
void primeSieve(int n) {
    for(int i = 2; i <= n; ++i) isPrime[i] = 1;
    for(int i = 2; i <= n; ++i) {
        if(isPrime[i]) prime.push_back(i);
        for(auto j : prime) {
            if(i * j > n) break;
            isPrime[i*j] = 0; // 埃氏筛
            if(!(i % j)) break; // 欧氏筛
        }
    }
}

「莫比乌斯筛」计算各整数的莫比乌斯函数的值，可以和素数一起筛。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int mu[MAX];
bool vis[MAX];
std::vector<int> prime;
void muSieve(int n) {
    mu[1]=1;
    for(int i = 2; i <= n; ++i){
        if(!vis[i]) mu[i] = -1, prime.push_back(i);
        for(auto j : prime) {
            if(i * j > n) break;
            vis[i*j] = 1;
            if(!(i % j)) break;
            else mu[i*j] = -mu[i];
        }
    }
}

数论函数(Number-Theoretic Function)

又称算术函数(Arithmetic Function)，指定义域为正整数的函数。

积性函数(Multiplicative Function)是对有的数论函数。常见的积性函数如下。

  • 除数函数(Divisor Function)：；
  • 单位函数(Unit Function)：；
  • 恒等函数(Identity Function)：；
  • 欧拉函数(Euler's Totient Function)：。

完全积性函数(Completely Multiplicative Function)是对任意、有的数论函数。

狄利克雷卷积(Dirichlet Product)

狄利克雷卷积是数论函数间的一种运算，数学形式如下。

狄利克雷卷积的代码实现如下。

1
2
3
4
5
void dirichlet(int n) {
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j * i <= n; ++j)
            h[i*j] += f[i] * g[j];
}

狄利克雷卷积满足交换律、结合律和分配律。两积性函数的狄利克雷卷积仍是积性函数。

莫比乌斯函数(Möbius Function)

莫比乌斯函数的数学形式如下。

莫比乌斯函数是积性函数，且满足。

二进制取幂(Binary Exponentiation)

又称「快速幂」。

1
2
3
4
5
6
7
8
9
10
LL mod = 10007;
LL quickpow(LL a, LL b) {
    LL re = 1;
    while(b) {
        if(b & 1) re = (re * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return re % mod;
}

循环右移(ROR; Rotate Right)

倒置法实现循环右移的代码如下。

1
2
3
4
5
6
7
8
9
10
11
void reverse(int* arr, int begin, int end) {
    --end;
    while(begin < end) swap(arr, begin++, end--);
}
void ror(int* arr, int n, int k) {
    k %= n;
    if(k == 0) return;
    reverse(arr, 0, n);
    reverse(arr, 0, k);
    reverse(arr, k, n - k);
}

汉诺塔(Tower of Hanoi)

可将一个搬动个盘子的问题，转换为两个搬动个盘子的问题。

1
2
3
4
5
6
7
8
enum Tower { A = 'A', B = 'B', C = 'C' };
void Hanoi(int n, Tower x, Tower y, Tower z) {
    if(n) {
        Hanoi(n - 1, x, z, y);
        // 移动塔x顶部的盘子至塔y顶部
        Hanoi(n - 1, z, y, x);
    }
}

霍纳法则(Horner's Rule)

又称「秦九韶算法」，用最少的乘法来计算多项式在点的取值。

若有如下的多项式。 由霍纳法则可得如下结果。

尺取法(しゃくとり法)

尺取法名称源于日本的尺蠖虫(シャクトリムシ)，其行动时身体屈伸如拱桥。尺取法又称双指针技巧(Two-Pointer Technique)，通过移动左、右端点来遍历一个数列，从而求解一个最短区间的算法。一般而言，尺取法的时间复杂度为。

例如，求正整数序列的最短连续子序列使各元素和大于等于某值。区间和小于该值时，右端右移，以使满足条件；区间和大于等于该值时，左端右移，更新答案。

弗洛伊德的乌龟和兔子(Floyd's Tortoise and Hare)

又称快慢指针(Fast & Slow Pointers)。快指针(Fast Pointer)即兔子，每次移动两步；慢指针(Slow Pointer)即乌龟，每次移动一步。如果链表存在环，那么快慢指针一定会相遇。

下例在长度为且元素位于区间中的数组内，找出存在且仅存在一个的重复元素。根据鸽巢原理(Pigeonhole Principle)(即「只鸽子被关在个鸽笼中，至少有一个笼子有至少两只鸽子」)，该数一定存在。

1
2
3
4
5
6
7
8
9
10
11
12
def find(arr):
    tortoise = arr[0]
    hare = arr[0]
    while True:
        tortoise, hare = arr[tortoise], arr[arr[hare]]
        if tortoise == hare: break
    ptr1 = arr[0]
    ptr2 = tortoise
    while ptr1 != ptr2:
        ptr1 = arr[ptr1]
        ptr2 = arr[ptr2]
    return ptr1

快慢指针相遇后，使一指针指向头，另一指针指向相遇点，每次移动一步，能在环的入口处再相遇。此例中，环的入口即重复的元素。

快速输入输出(Fast I/O)

1
2
3
4
5
6
7
8
9
10
11
12
13
int read() {
    int x = 0, sign = 1;
    char c = getchar();
    while(c > '9' || c < '0') {
        if(c == '-') sign = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * sign;
}