0. 算法第四版的笔记
这篇博客是基于《算法第四版》使用Java语言实现书中各种数据结构及算法的。博客本身大部分都是基于书上的讲解摘抄作为笔记，习题只实现了小部分。这里有两个比较不错的动态化的图示的算法演示网站。
网站1：
Data Structure Visualizations:
网站2：
[ VisuAlgo]
2. 排序
2.1 选择排序
选择排序的思想是：首先找到数组中最小的那个元素，其次，将它和数组中的第一个元素交换位置，然后再在剩下的元素中找到最小的元素，将它与第二个元素进行交换，如此往复，直到整个数组都是有序的。
2.2 冒泡排序
冒泡排序的思想是：比较列表的相邻的数，如果前面的比后面的要大，那么就交换这两个，一趟排序完成之后，则无序区减少一个数，有序区增加一个数。
2.3 插入排序
插入排序是一种最简单的排序方法，它的基本思想就是将一个记录插入到已经排好序的有序列表中，从而一个新的、记录增加1的有序表。
2.4 希尔排序
希尔排序思想来自插入排序，只不过不像插入排序那样只改变相邻的元素，而是交换不相邻的元素。希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组编织在一起组成的一个数组，如果h很大，我们就能够将元素移动到很远的地方，为实现更小的h有序创建方便。
简单来讲，分组排序就是首先以一定的间隔（通常是数组的一半长度），对组内的元素进行排序，然后不断减半这个间隔h，直到1.
2.5 快速排序
快速排序是对冒泡排序的一种改进，通过多次比较和交换来实现排序，流程如下：
（1）首先设定一个分界值，通过该分界值将数组分为左右两部分。
（2）将大于或等于分界值的数据集中到数组右边，小于分界值的数值集中到数组的左边。此时，左边部分各个元素都小于分界值，右边元素都大于等于分界值。
（3）然后，左边和右边的数据可以独立排序，对于左侧的数据，又可以取一个分界值，将该部分数据分为左右两部分，同样在左边放较小的值，右边放置较大的值。右侧的数据可以做类似的处理。
（4）重复上述步骤，可以看出这是个递归的定义。通过递归将左侧部分排好序之后，再递归排好右侧部分的顺序，当左右两个部分的数据排序完成之后，整个数组排序完成。
2.6 堆排序
首先堆是一个完全近似二叉树的结构，并且同时满足堆积的性质，即子结点的键值或者索引总是小于或者大于它的父节点。
算法流程：
- 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或者小顶堆，大顶堆是节点大于叶子结点的数据，大顶堆用于升序排序
- 将堆顶元素与末尾元素交换，将最大元素沉到数组末尾
- 重新调整结构，使其满足堆的定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
2.7 归并排序
归并算法的思想是：采用分治的思想，将已经有序的两个子序列合并得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。（1）把长度为n的输入序列分为两个长度为n/2的子序列；（2）对这两个子序列分别采用归并排序；（3）将两个排好序的子序列合并成一个最终的排序序列
2.8 桶排序
其实基数排序和计数排序都是基于桶排序的思想发展来的。工作原理是将数组分到有限数量的桶子里面，每个桶再分别进行排序（使用别的算法或者递归继续桶排序）。若待排序的记录的关键字在一个明显有限的范围内时，可以设计有限个有序桶，每个桶只能装预置对应的值，顺序输出各桶的值，将得到有序的序列。简单来说，在我们可以确定需要排列的数组范围时，可以生成该数值范围内有限个桶去对应数组中的数，然后我们将扫描的数值放入匹配的桶里的行为，可以看做是分类，在分类完成后，我们需要依次按照桶的顺序输出桶内存放的数值，这样就完成了桶排序。
2.9 基数排序
桶排序的一种，非比较排序，多关键字排序。基本操作是：先找出数据中心最大的位数，然后从低位开始排序，收集已排序的数据，直到最高位排序完成。
算法的流程为：（1）先计算出数据的最大位数；（2）先从低位开始排序，再从高位开始排序，收集已经排序的数据；（3）不断从低位到高位，对数据进行排序，直到最高位已经排好，排序完成。
2.10 计数排序
假设输入的线性表L的长度为n，L=L1,L2,..,Ln；线性表的元素属于有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；则计数排序可以描述如下：
1、扫描整个集合S，对每一个Si∈S，找到在线性表L中小于等于Si的元素的个数T(Si)；
2、扫描整个线性表L，对L中的每一个元素Li，将Li放在输出线性表的第T(Li)个位置上，并将T(Li)减1。
2.11 优先队列
优先队列是一种抽象数据类型，它表示了一组值和对这些值的操作。优先队列的最重要的方法就是删除最大元素以及插入元素。
如果我们使用指针来表示堆有序的二叉树，那么每个元素都需要三个指针来找到其上下节点，父节点和两个子结点各需一个。完全二叉树只用数组而不需要指针就可以表示。二叉堆是一组能够能够用有序的完全二叉树排序的元素，并在数组中安照层级存储（不使用数组的第一个位置）。一颗大小为N的完全二叉树的高度为\(\lfloor lg N \rfloor\)。
对于一个含有N个元素的基于堆的优先队列，插入元素操作只需要不超过\((lgN+1)\)次比较，删除最大元素的操作只需要不超过\(2lgN\)次操作。
2.12 单调栈
单调栈是指栈内的元素，从栈底到栈顶都是单调递增或者单调递减的。如果有新元素的入栈，栈调整过程中，会将所有破坏单调性的元素出栈，并且出栈的元素不会再次入栈。由于每个元素只有一次入栈和出栈的操作，所以单调栈的维护时间复杂度是\(O(n)\)
递增栈中可以找到元素左右两侧比自身小的第一个元素。假设从栈底到栈顶是递增的，当有新元素入栈。对于出栈元素来说，找到右侧第一个比自身小的元素。对于新元素来说，等待所有破坏递增顺序的元素出栈后，找到左侧第一个比自身小的元素。
1 | import java.util.ArrayList; |
3. 查找
3.1 符号表
符号表最主要的目的就是将一个键和一个值关联起来。用例能够将一个键值对插入符号表并希望在之后能够从符号表的所有键值对中按照键直接找到相对应的值。
所有的实现都基于以下的规则：
- 每个键只对应一个值（表中不允许存在重复的键）
- 当用例代码向表中存入的键值对和表中已有的键（或者关联的值）冲突时，新的值会代替旧的值
为了方便用例处理表中的所有键值，会在第一行加上implements Iterable
无序链表中的顺序查找
符号表中使用的数据结构中的一个简单选择就是链表，每个节点存储一个键值对。
实现的代码：
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
34public class SequentialSearchST <Key, Value>{
private Node first;//链表首节点
private class Node{
Key key;
Value val;
Node next;
public Node(Key key, Value val, Node next) {
this.key = key;
this.val = val;
this.next = next;
}
}
public Value get(Key key){
//给定查找的值，返回相关联的值
for (Node x = first; x != null; x = x.next){
if (key.equals(x.key))
return x.val;//命中
}
return null;//未命中
}
public void put(Key key, Value val){
//查找给定的键，找到则更新其值，否则在表中新建节点
for (Node x = first; x != null; x = x.next){
if (key.equals(x.key)){
x.val = val;
return;//命中，更新
}
}
first = new Node(key, val, first);//未命中，新建节点
}
}基于链表的查找是非常低效的，可以使用二分查找的方法，不过二分查找就必须要求查找的时候。下面的算法中最重要的就是rank()函数，这个函数就是来定位给定的值的位置的，正是可以轻松的定位，给其他查找的时候的代码简化了。在N个键的有序数组中进行二分查找最多需要\(lg N + 1\)次比较。
二分查找虽然说减少了比较的次数，但是还是无法减少运行所需的时间。因为它无法改变的事实是：在键是随机排列的情况下，构造一个基于有序数组的符号表所需的访问数组的次数仍然是长度的平方级别，虽然在实际的情况中不是随机的，但是还是很好的符合这个分布。
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125public class BinarySearchST <Key extends Comparable<Key>, Value>{
//这里的key是继承自comparable对象，所以可以比较大小
private Key[] keys;
private Value[] values;
private int N;
public BinarySearchST(int capacity) {
keys = (Key[]) new Comparable[capacity];
values = (Value[]) new Object[capacity];
}
public int size(){
return N;
}
public boolean isEmpty(){
return N == 0;
}
public Value get(Key key){
if (isEmpty())
return null;
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0)
return values[i];//根据排序来定位
else
return null;
}
public void put(Key key, Value val){
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0){
values[i] = val;
return;//更新
}
for (int j = N; j > i; j --){
keys[j] = keys[j - 1];
values[j] = values[j - 1];
}
keys[i] = key;
values[i] = val;
N ++;
/**
* assert condition;
* 这里condition是一个必须为真(true)的表达式。如果表达式的结果为true，那么断言为真，并且无任何行动
* 如果表达式为false，则断言失败，则会抛出一个AssertionError对象。这个AssertionError继承于Error对象，
* 而Error继承于Throwable，Error是和Exception并列的一个错误对象，通常用于表达系统级运行错误。
*/
assert check();
}
public void delete(Key key){
if (isEmpty())
return;
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0){//定位元素
for (int j = 1; j < N - 1; j++) {
keys[j] = keys[j + 1];
values[j] = values[j + 1];
}
N --;
keys[N] = null;
values[N] = null;
}
assert check();
}
public Key min(){
return keys[0];
}
public Key max(){
return keys[N - 1];
}
public Key ceiling(Key key){
int i = rank(key);
return keys[i];//取值
}
public Key floor(Key key){
int i = rank(key);
if (i < N){
if (keys[i].compareTo(key) == 0)
return key;
else if (i > 0)
return keys[i - 1];
}
return null;
}
public int rank(Key key){
//返回表中小于给定键的键的数量
int lo = 0, hi = N - 1;
while (lo < hi){//二分查找，基于有序数组
int mid = lo + (hi - lo) / 2;
int cmp = key.compareTo(keys[mid]);
if (cmp < 0)
hi = mid - 1;
else if (cmp > 0)
lo = mid + 1;
else
return mid;
}
return lo;
}
public Key select(int k){
return keys[k];//返回第k个元素
}
public boolean check(){
return isSorted() && rankCheck();
}
public boolean isSorted(){
for (int i = 1; i < size(); i++) {
if (keys[i].compareTo(keys[i - 1]) < 0)
return false;
}
return true;
}
public boolean rankCheck(){
for (int i = 0; i < size(); i++) {
if (i != rank(select(i)))//检查是否标号对应
return false;
}
for (int i = 0; i < size(); i++) {
if (keys[i].compareTo(select(rank(keys[i]))) != 0)
return false;//检查值是否对应
}
return true;
}
}一般情况下二分查找都比顺序查找快的多，它也是众多实际应用中程序中的最佳选择，对于一个静态表来说，将其在初始化时就排序是值得的。当然，如果一个数据集的插入和查找操作是混合进行的话，那么二分查找就不再适合了。我们需要在构造庞大的符号表的同时能够任意插入或者删除检制度，同时也要能够完成查找操作，而使用二叉查找树就能够将查找和插入的操作的算法复杂度都降为对数级别。
3.2 二叉查找树
在二叉查找树中，每个节点包含了一个键和一个值，键之间也有顺序之分以支持高效的查找。二叉查找树的每个节点都含有一个Comparable的键（以及相关联的值），且每个节点的值都大于其左子树的任意结点的键而小于右子树的任意结点的键。
首先这个地方一直要使用到第一章所提到的队列的实现，这里给出了本书泛型的队列，使用的是链表的实现。
1 | import java.util.Iterator; |
具体实现二叉查找树的代码如下，代码中尤其值得注意的是二叉树的删除和插入结点！！！
1 | public class BST<Key extends Comparable<Key>, Value> { |
3.3 平衡查找树
前面的数据结构和算法中，最坏的情况的性能依旧很糟糕，平衡查找树是一种二分查找树，能够保证无论如何构造它，运行时间都是对数级别的。
2-3查找树
将一颗标准的二叉查找树中的节点称为2-节点，其含有一个键和两条链接。而现在引入3-节点，它含有两个键和三条链接。2-节点和3-节点中的每条链接都对应着其中保存的键所分割产生的一个区间。
一颗2-3查找树要么为一颗空树，要么由以下节点组成：
- 2-节点：含有一个键（及其对应的值）和两条链接，左链接指向的2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。
- 3-节点：含有两个键（及其对应的值）和三条链接，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点。
一颗完美二叉树的所有空链接到根结点的距离都应该是相同的。但是上述的数据结构的表示方式实现大多数的操作并不方便，因为需要处理的情况很多。所以引出下面的红黑树。
红黑二叉查找树
红黑二叉查找树背后的基本思想是用标准的二叉查找树和一些额外的信息（替换3-节点）来表示2-3树。将树中的链接分为两类：红链接将两个2-节点连接起来构成一个3-结点，黑链接则是2-3树中的普通链接。将3-节点表示为由一条左斜的红色链接（两个2-结点其中之一是另一个的左子节点）相连的两个2-节点。如下图所示：
这种表示的方法的优点是，无序修改就可以直接使用标准二叉查找树的get()方法。（意思就是把2-3树中的3-节点拆分了，拆分得做记号，也就是将较小的那个节点作为较大的结点的左子节点，并且接下去的子结点的划分也要满足平衡二叉树的定义）
以下摘抄自文章：[https://www.jianshu.com/p/e136ec79235c]
红黑树满足的性质主要有以下五点：
每个节点要么是黑色要么是红色
根结点是黑色
每个叶子结点是黑色，而且是空的
每个红色节点的两个子结点一定都是黑色的
任一节点到每个叶子结点的路径都包含数量相同的黑节点（这个可以推出来，如果一个结点存在黑子节点，那么该结点一定有两个子结点）
简单的红黑树结构
简单的红黑树结构如上图所示，可以看出红黑树不一定是一个完美平衡的二叉查找树。因为其左子树和右子树的高度并不一定是一致的，但是都包含相同数量的黑节点，称之为黑色完美平衡。
红黑树的自平衡
- 左旋：以某个节点作为支点（旋转节点），其右子结点变为旋转的父节点，右子结点的左子节点变为旋转节点的右子结点，左子节点保持不变。
- 右旋：以某个节点作为支点（旋转节点），其左子节点变为旋转节点的父节点，左子节点的右子结点变为旋转节点的左子节点，右子结点保持不变。
- 变色：节点的颜色由红变黑或者由黑变红。
红黑树的左旋
红黑树的右旋
左旋只会影响旋转节点和其右子树的结构，把右子树的结点往左子树挪动了。而右旋只会影响旋转节点和其左子树的结构，把左子树的结点往右子树挪动了。所以旋转操作只是局部的，直观上理解就是：当一边子树的结点少了，那么向另外一边子树借一点节点。红黑树总是通过旋转和变色来达到自平衡。
红黑树的查找和二分查找树是一样的，接下里说一下插入和删除。
红黑树的插入
插入包含两个工作：一个是插入的位置，另一个是插入后自平衡。插入位置查找跟红黑树的查找没差太多，只是插入的颜色默认是红色的，因为这样的话就保证了我们插入之后的黑色平衡没有被破坏。步骤如下：
红黑树插入位置查找
红黑树的插入主要有以下这么多类：
插入结点的关系结点表示
红黑树为空树。这个情况最简单了，直接返回一个黑色的根结点即可。
当插入的结点key已经存在。这个操作也很简单，直接把插入的结点设置为将要替代结点的颜色，然后更新结点的值。
当插入的结点的父节点是黑色的结点。这个也很简单，由于插入的结点是红色的，不会影响红黑树的平衡，直接插入即可，无需做自平衡。
插入结点的父节点为红色节点。这种情况就很复杂了。
4.1 叔叔结点存在并且为红结点。
叔叔结点为红色的话，那么祖父节点肯定就是黑色的了。那么此时插入子树的红黑层数的情况是：黑红红。最简单的处理方式就是把其改成：红黑红。
插入情景4.1_1
插入情景4.1_2可以看到，已经把PP节点设置为红色了，如果PP的父节点是黑色，那么无序再做任何处理的操作。但是如果PP的父节点是红色，此时红黑树已经不平衡了，所以还需要把PP当做新的插入结点，继续做插入操作自平衡处理，直到平衡为止。
PP如果为根结点，我们必须将PP设置为黑色，那么树的红黑结构变为：黑黑红。换句话说，从根结点到叶子结点的路径中，黑色结点增加了。这也是唯一会增加红黑树黑色结点层数的插入情景。红黑树的生长是自底向上的，这点不同于普通的二叉查找树，普通的二叉查找树的生长是自顶向下的。
4.2 叔叔结点不存在或者为黑结点，并且插入结点的父亲结点是祖父结点的左子结点
单纯从插入的角度来看，叔叔结点非红就是叶子结点（也就是空节点）。因为如果叔叔结点为黑结点，而父节点为红结点，那么叔叔结点所在的子树的黑色结点就比父节点所在的子树多了，这不满足红黑树的性质5。
4.2.1 插入结点是其父节点的左子节点
处理为：将P设为黑色，PP设为红色，对PP进行右旋。
插入情景4.2.14.4.2 插入结点是其父节点的右子结点
处理为：对P进行左旋，将P设置为插入结点，得到4.2.1的情况，然后进行4.2.1的处理。
插入情景4.2.24.3 插入结点不存在或者为黑结点，并且插入结点的父节点是祖父结点的右子结点
4.3.1 插入结点是其父节点的右子结点
处理为：将P设为黑色，将PP设为红色，对PP进行左旋
插入情景4.3.14.3.2 插入结点是其父节点的左子节点
处理为：对P进行右旋，将P设置为插入结点，得到情景4.3.1，进行情景4.3.1的处理
插入情景4.3.2
3.4 散列表
4. 图
4.1 无向图
图的概念在研究工作中已经很透彻了，介绍一些数据结构的概念。
- 自环：已一条连接一个顶点和其自身的边。
- 平行边：连接同一对顶点的两条边。
- 树：一幅无环的连通图。
- 森林：互不相连的树组成的集合叫做森林。
- 二分图：能够将所有的结点分为两部分的图，其中图的每条边所连接的两个顶点都分别属于不同的部分。
算法第四版这本书给出了一些实现图算法的API，比起networkx库给的要简单的多，不过对于学习还是可以的。
图的表示方法：
- 邻接矩阵。使用一个\(V \times V\)的布尔矩阵，当顶点v和顶点w之间有相连接的边时，定义v和w的元素值为true，这种不适合大规模的网络。
- 边的数组。使用一个Edge类，它含有两个int实例变量。但是这种又实现不了API中的adj()方法，检查所有的连边的结点。
- 邻接表数组。使用一个以顶点为索引的列表数组，其中的每个元素都是和该顶点相邻的顶点列表。
邻接表数组
邻接表数组这一数据结构就是把每个顶点的所有相邻结点都保存在该结点对应的元素所指向的一张链表中。要添加一条连接v和w的边，我们将w添加到v的邻接表中，并把v添加到w的邻接表中，这种graph的实现性能有如下的特点：
- 使用的空间和V+E成正比
- 添加一条边所需的时间为常数
- 遍历顶点v的所有相邻顶点所需的时间和v的度数成正比，处理每个相邻顶点所需的时间为常数
1 | public class Graph { |
这个graph的实现使用的是一个由顶点索引的整型表数组。第二个构造函数从输入流中读取一幅图，开头是V，然后是E，再然后是一列整数对，大小在0到V-1之间。
4.1.1 图的搜索
- 深度优先搜索：是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次
- 广度优先搜索：系统地展开并检查图中的所有结点，以寻找结果。
深度优先搜索和广度优先搜索的示例图如下所示：
深度优先搜索与广度有限搜索
1 | /** |
public DepthFirstSearch(Graph G, int s) {
marked = new boolean[G.V()];
dfs(G, s);
}
public void dfs(Graph G, int v){
marked[v] = true;//标记为已访问
count ++;
for (Integer w : G.adj(v)) {
if (! marked[w])
dfs(G, w);//以中心节点发散式的去寻找,一直递归的以当前节点为中心节点去往深处走
}
}
public boolean marked(int w){
return marked[w];
}
public int count(){
return count;
}}
1 |
|
广度优先搜索能够解决的问题是：单源最短路径问题，给定一个图和一个起点s，要找到s到v的最短路径。在深度优先搜索中，使用的是后进先出的栈来描述压栈和走迷宫时县探索相邻的通道，从有待搜索的通道中选择最晚遇到过的那条。在广度优先搜索中，使用先入先出的队列来代替栈，按照与起点的距离的顺序来遍历所有的节点。
1 | /** |
深度优先搜索和广度优先搜索的差异仅仅在于从数据结构中获取下一个节点的规则，对于广度优先搜索来说是最早加入的顶点，对于深度优先来说是最晚加入的结点。深度优先就像是一只苍蝇在一个迷宫里面乱逛，广度优先就像是往迷宫里面灌水。
连通分量的实现：很简单的，看看得了、
1 | public class CC { |
4.1.2 union-find算法
理论上union find算法比深度优先搜索算法要慢，因为它不能保证所需的时间是常数，而union find需要。但是在实际应用中，这点差异微不足道，实际上union-find算法其实更快，因为它不需要完整构造并表示一幅图。我们在完成只需要判断连通性或者需要完成有大量连通性查询和插入操作混合等类似的任务时，倾向于使用union-find算法。而深度优先搜索则更适合实现图的抽象数据类型，因为它能更有效地利用已有的数据类型。这个地方讲讲union-find算法，其实是在第一章讲的。
引入一个动态连通性问题，问题的输入是一列整数对，其中每个整数都表示一个某种类型的对象，对整数p，q可以被理解为"p和q是相连的"。相连会有以下的性质：
- 自反性：p和p是相连的
- 对称性：如果p和q是相连的，那么q和p也是相连的
- 传递性：如果p和q是相连的，且p和r也是相连的，那么p和r也是相连的
等价关系将对象分为多个等价类，当且仅当两个对象相连时他们才属于同一个等价类。我们的目标就是编写一个程序来过滤掉序列中所有无意义的整数对（两个整数对都来自同一个等价类中），只有当读取的p和q在所有的已知的整数对中都不能说明他们是相连的时候，才会添加这个整数对。
本书将对象称为触点，将整数对称为连接，将等价类称为连通分量或者是简称分量。本书的API中实现了union(),find(),connected()和count()方法，分别表示在p和q之间添加连接，找到p所在的分量的标识符，判断p和q是否存在于同一个分量中，以及连通分量的数量。
quick-find算法
一种方法是保证当且仅当id[p]等于id[q]时p和q才是连通的。在同一个连通分量中的所有触点在id[]中的值必须全部相同。算法比较简单，代码如下：
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
41public class UF {
private int[] id;//连通分量id，触点作为索引，表示触点属于哪个连通分量
private int count;
public UF(int N) {
count = N;
id = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;//初始化，就当做有N个连通分量
}
}
public int count(){//整个的连通分量的数目
return count;
}
public boolean connected(int p, int q){//判断两个触点是否连接
return find(p) == find(q);
}
public int find(int p){//找到p所在的分量的标识符
return id[p];
}
/**quick-find算法
* 意思是当我们输入一个连通之后，会打通这个里面所有的连着的
* **/
public void union(int p, int q){
//将p和q归并到相同的分量中
int pID = find(p);
int qID = find(q);
if (pID == qID)
return;//如果p和q已经在相同的分量中，则不需要求任何行动
//不存在相同的分量，那么需要将p的分量重命名为q的名称
for (int i = 0; i < id.length; i++) {
if (id[i] == pID)
id[i] = qID;
}
count --;//要减少一种分量
}
}这个算法中每次调用find()函数需要访问数组一次，而归并两个分量的union()操作需要访问数组在(N+3)到(2N+1)之间。我们至少要\((N+3)(N-1)\)次的访问数组，也就是平方的量级，不适用于大量的数据集。
quick-union算法
这个算法相当于上述算法的改进，id[]数组还是以触点作为索引的，但是他的值的含义不一样。每个触点对应的id[]元素都是同一个分量中的另一个触点的名称，当然也可能是他本身，将这种关系称为链接，可以认为(p,q)二元组是一个边。
在上面的find()算法中，从给定的触点开始，由它的链接得到另一个触点，再由这个触点的链接达到第三个触点，如此延伸达到最后一个触点，也就是根触点，即链接指向自己的触点。当且仅当分别由两个触点开始的这个过程达到了同一个根触点时他们存在于同一个连通分量中。
而相应的union算法就变为：我们由p，q的链接分别找到他们的根触点，然后只需将一个触点链接到另一个触点即可将一个分量重命名为另一个分量。
quick-union算法图解如下：
quick-union算法图解</center
代码实现如下：
1 | public class QuickUnion { |
将结点连接起来的话，quick-union算法是会得到一棵树的，id[]数组用父链接额度形式表示了一篇森林。无论我们才能够任何触点所对应的结点开始跟随链接，最终都将达到该结点的树的根结点。而union-find算法在最坏的情况下的时间复杂度也是平方级别的。假如输入的整数对是有序的，0-1,0-2,0-3等等，N-1对的触点更新之后我们的树的高度将会是N-1，退化成了单链表，这就构成了该算法的最坏情况。改正的话需要下面的加权quick-union算法。
加权quick-union算法
这个算法考虑的是，与其在union()中随意将一棵树连接到另一棵树，我们现在会记录每棵树的大小并总是将较小的树连接到较大的树上。
1 | public class WeightedQuickUnionUF { |
对于N个触点，加权quick-union算法构造的森林中的任意结点的深度最多为\(lgN\)。
路径压缩的加权quick-union算法
路径压缩的quick-union算法就是在find()方法中添加一个循环来将从p到根结点的路径上的每个触点都连接到根结点。这样我们得到的树将会是一棵几乎完全扁平化的树。路径压缩的加权quick-union算法是最优的算法。
1 | public class CompressedWeightedQU { |
4.2 有向图
在有向图中，边是单向的，每条边所连接的两个顶点都是一个有序对，它们的邻接性是单向的。有向图中一个顶点的入度为由该顶点指出的边的总数；一个顶点的入度为指向该顶点的边的总数。规定每个顶点都能达到它自己，除此之外，在有向图中由v能到达w并不意味着由w也能达到v。
这里实现DiGraph的代码如下，其中reverse()方法返回有向图的一个副本，将其所有的边都反转。
1 | public class DiGraph { |
4.2.1 有向图中的可达性
单点可达性：给定一幅有向图和一个起点s，回答是否存在一条从s到达给定顶点v的有向路径。多点可达性：给定一幅有向图和顶点的集合，回答是否存在一条从集合中的任意顶点到达给定顶点v的有向路径。
1 | public class DirectedDFS { |
这里使用的有向图，构建的时候只有一点是不一样的，也就是我们只单方向的把一个结点加入到了adj[]数组中。
1 | public void addEdge(int v, int w){//添加边，v->w的连边 |
此外在有向图中我们还倾向于寻找是否有有向环以及判断是否有向无环图，这里系统维护的递归调用的栈表示的正是当前正在遍历的有向路径。一旦我们找到了一条有向边\(v \to w\)且w已经存在于栈中，就找到了一个环，因为栈表示的是一条从w到v的路径，而\(v \to w\)正好补全了这个环。
1 |
|
4.2.2 有向图中的强连通性
强连通性定义为：如果两个顶点v和w互相是可达的，则称它们是强连通的。同样的，强连通也存在如下的性质：
- 自反性：任意顶点v和自己都是强连通的
- 对称性：如果v和w是强连通的，那么w和v也是强连通的
- 传递性：如果v和w是强连通的且w和x也是强连通的，那么v和x也是强连通的
强连通性将所有的顶点分为了一些等价类，每个等价类都是相互均为强连通的顶点的最大子集组成的，我们将这些子集定义为强连通分量。
首先这个书给出了一个有向图中基于深度优先搜索的顶点排序，给出了所有顶点的前序排列，后续排列以及逆后序排列。
1 | public class DepthFirstOrder { |
这里给出的是Kosaraju算法吗，将会完成以下任务：
- 在给定的一幅有向图中，使用DepthFirstOrder来计算它的反向图\(G^R\)的逆后序排序
- 在G中进行标准的深度优先搜索，但是要按照刚才计算得到的顺序而非标准的顺序来访问所有的未被标记的顶点
- 在构造函数中，所有在同一个递归dfs()调用中被访问到的顶点都在同一个强连通分量中，将他们按照和CC相同的方法识别出来
1 | public class KosarajuSCC { |
Kosaraju算法的预处理所需的时间和空间与V+E成正比且支持常数时间的有向图强连通性的查询。
4.3 最小生成树
生成树的定义为：图的生成树是它的一棵含有其所有的顶点的无环连通子图。一幅加权图的最小生成树（MST）是它的一棵权值（书中所有边的权值之和）最小的生成树。
本书做了以下的一些约定：
- 只考虑连通图
- 边的权重不一定表示距离，可以理解为代价
- 边的权重可能是0或者负数
- 所有边的权重都各不相同
树具有两个性质：
- 用一条边连接树中的任意两个顶点都会产生一个新的环
- 从树中删除一条边将会得到两棵独立的树
切分定理：在一幅加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图的最小生成树。
4.3.1 Prim算法
Prim算法能够得到任意加权连通图的最小生成树。本书使用以下方法表示树中的顶点、边和横切边。
- 顶点：使用一个由顶点索引的布尔数组marked[]，如果顶点v在树中，那么marked[v]的值为true
- 边：选择使用以下两种数据结构之一：一条队列mst来保存最小生成树的边，或者一个由顶点索引的Edge对象的数组edgeTo[]，其中edgeTo[v]为将v连接到树中的Edge对象。
- 横切边：使用一条优先队列MinPQ
来根据权重比较
prim算法的主要流程就是如下：
primAlgorithm_1
primAlgorithm_2
prim算法的延迟实现计算一幅含有V个顶点和E条边的连通加权无向图的最小生成树所需的空间与E成正比，所需的时间与\(ElogE\)成正比。
1 | public class LazyPrimMST { |
当然上述的算法还是可以改进的，可以尝试从优先队列中删除失效的边，这样优先队列就只含有树顶点和非树顶点之间的横切边，但其实还可以删除更多的边。我们感兴趣的边只是连接树顶点和非树顶点中权重最小的边。当我们将顶点v添加到树中时，对于每个非树顶点w产生的变化只可能使得w到最小生成树的距离更近了。我们不需要再优先队列中保存所有从w到树顶点的边，而只需要保存其中权重最小的那条，在将v添加到树中后检查是否需要更新这条权重最小的边（因为v-w的权重可能更小）。我们只需要遍历v的邻接链表就可以完成这个任务，只会在优先队列中保存每个非树顶点w的一条边：将它与树中的顶点连接起来的权重最小的那条边。
将LazyPrimMST中的marked[]和mst[]替换为两个顶点索引的数组edgeTo[]和distTo[]，它们具有以下的性质：
- 如果顶点v不在树中但至少有一条边和树相连，那么edgeTo[v]是将v和树连接的最短边，distTo[v]为这条边的权重。
- 所有这类顶点v都将保存在一条索引优先队列中，索引v关联的值是edgeTo[v]的边的权重。
即时的Prim
即时的Prim1
即时的Prim2
即时的Prim3
实现上述步骤的代码如下：
1 | public class PrimMST { |
4.3.2 Kruskal算法
kruskal算法1
kruskal算法2
kruskal算法3
kruskal算法思想相当简单，kruskal算法构造最小生成树的时候也是一条边一条边地构造，但不同的是它寻找的边会连接一片森林的两棵树。我们从一片由V棵单顶点的树构成的森林开始并不断地将两棵树合并（用可以找到的最短边）直到只剩下一棵树，它就是最小生成树。代码实现如下：
1 | public class kruskal { |
4.4 最短路径
4.4.1 Dijkstra算法
最短路径就是找到从一个顶点到另一个顶点的成本最小的路径。最短路径的性质如下：
- 路径是有向的，最短路径要考虑到各条边的方向
- 权重不一定等价于距离
- 并不是所有顶点都是可达的
- 负权重会使得问题更加复杂
- 最短路径一般都是简单的
- 最短路径不一定是惟一的
- 可能存在平行边或者自环
本书的重点是单点最短路径问题，其中给出了起点s，计算的结果是一棵最短路径树(SPT)，它包含了顶点s到所有可达的顶点的最短路径。给定一幅加权有向图和一个顶点s，以s为起点的一棵最短路径树是图的一幅子图，它包含s和从s可达的所有顶点。这棵有向树的根结点为s，树的每条路径都是有向图中的一条最短路径。
首先我们得要有个有向边的集合类，用来构建加权有向图：
1 | public class DirectedEdge { |
根据有向边构建的有向图为：
1 | public class EdgeWeightedDigraph { |
最短路径的数据结构：
- 最短路径树中的边。使用一个由顶点索引的DirectedEdge对象的父链接数组edgeTo[]，其中edgeTo[v]的值为树中连接v和它的父节点的边（也是从s到v的最短路径上的最后一条边）。
- 到达起点的距离。需要一个由顶点索引的数组distTo[]，其中distTo[v]为从s到v的已知的最短路径的长度。
4.4.1.1 边的松弛：
一开始我们只知道图的边和他们的权重，distTo[]中只有起点对应的元素的值为0，其余元素的值均被初始化为double.POSITIVE_INFINITY.更新的时候会用到松弛技术，定义为：松弛\(v \to w\)意味着检查从s到w的最短路径是否先从s到v，然后再从v到w。如果是的话，则根据这个情况更新数据结构的内容。由v到达w的最短路径是distTo[v]与e.weight()之和，如果这个值不小于distTo[w]，称这条边失效了并将它忽略。如果这个值更小，则更新数据。
1 | private void relax(DirectedEdge e){ |
边的松弛化
4.4.1.2 顶点的松弛
实现顶点的松弛如下所示，从任意distTo[v]为有限值的顶点v指向任意distT[]为无穷的顶点的边都是有效的。如果v被放松，那么这些由小编都会被添加到edgeTo[]中。某条从起点指出的边将会是第一条被加入edgeTo[]中的边。
1 | private void relax(EdgeWeightedDigraph, int v){ |
顶点的松弛
4.4.1.3 图解和代码
Dijkstra算法的图解流程主要如下，主要的思想就是在当前遍历到的节点更新其到要查找的权重距离，找出当前最小的，作为新添加的边。
Dijkstra算法1
Dijkstra算法2
Dijkstra算法3
Dijkstra算法4
代码实现如下：
1 | public class DijkstraSP { |
实现任意顶点之间的最短路径的代码如下：
1 | public class DijkstraAllPairsSP { |
4.4.2 Bellman-Ford算法
这个算法适用于无环加权图中，它的特点是：
- 能够在线性时间内解决单点最短路径问题
- 能够处理负权重的边
- 能够解决相关的问题
4.4.2.1 无环加权图的最短路径树
在查找无环加权图的最短路径树的时候，可以使用以下的方法。这个方法首先通过深度优先搜索得到顶点的拓扑排序，然后根据这个去遍历节点，并更新使得路径最短，如下面的图所示：
无环加权有向图最短路径1
无环加权有向图最短路径2
无环加权有向图最短路径3
1 |
|
还有一类问题是考虑在无环加权有向图中寻找最长路径的问题，边的权重可正可负。解决无环加权有向图中的最长路径问题的时间与\(E+V\)成正比。
4.4.2.2 图解和代码
bellman-ford算法对图进行\(V-1\)次的松弛操作，得到所有可能的最短路径。其优于Dijkstra算法的地方在于边的权重可以是负值，实现简单。但是缺点就是时间复杂度高，需要\(O(VE)\)。Dijkstra算法关注的是点，而bellman-ford关注的是边。
算法描述为：
- 创建源顶点v到图中所有顶点的距离的集合，为图中的所有顶点指定一个距离值，初始化均为无穷，源顶点的距离为0；
- 计算最短路径，执行\(V-1\)次遍历
- 对于图中的每条边：如果起点u的距离d加上边的权值w小于终点v的距离d，则更新终点v的距离值d；
- 检测图中是否有负权边形成了环，遍历图中的所有边，计算u至v的距离，如果对于v存在更小的距离，则说明存在环。
bellman-ford算法的图解如下：
bellman-ford算法1
bellman-ford算法2
bellman-ford算法的代码如下：
1 | public class BellmanFordSP { |
5. 字符串
5.1 字符串排序
字符串的排序主要有两种：
- 第一种方法会从右到左检查键中的字符，这种方法一般称为低位优先(LSD)的字符串排序。如果将一个字符串看做一个256进制的数字，那么从右向左检查字符串就等价于先检查数字的最低位。这种方法最适合用于键的长度都相同的字符串排序的应用。
- 第二种方法会从左到右检查键中的字符，首先查看的是最高位的字符。这些方法通常称为高位优先(MSD)的字符串排序。高位优先的字符串排序和快速排序类似，因为他们都会将需要排序的数组且分为独立的部分并递归的用相同的方法处理子数组来完成排序。他们的区别在于高位优先的字符串排序算法在切分的时候仅使用键的第一个字符，而快速排序的比较则会涉及键的全部。
5.1.1 键索引计数法
适用于小整数键的简单排序方法，假设数组\(a[]\)中的每个元素都保存了一个名字和一个组号，其中组号在0到R-1之间，以组号为键进行分组排序。
- 频率统计：使用int型数组计算每个键出现的频率；
- 数据分类：将\(count[]\)来计算每个键在排序结果中的起始位置；
- 回写：将排序数组\(aux[]\)结果复制回原数组；
- 命题：键索引计数法排序N个键为0到R-1之间的整数的元素需要访问数组\(11N+4R+1\)次；
1 | package Chapter5.Part5_1; |
分析一下索引计数法的四个步骤：
1.计算频率
1 | for (int i = 0; i < N; i++) |
遍历所有的字符串，d为字符串的第d个字符。也就是统计每个字符的个数。
2.将频率转换为下标，也就是count数组中后一位总是加上前一位。
1 | count[r+1] += count[r]; |
3.数据分类
1 | for (int i = 0; i < N; i++) |
需要一个辅助数组aux，用来暂时存储排序的数据。把数据放入辅助字符串数组，全部放入时已经形成有序了。
5.1.2 低位优先的字符串排序
如果字符串的长度均为W，那就从右向左以每个位置的字符作为键，用索引计数法将字符串排序W遍。低位优先字符串排序从右向左检查字符，要求待排序的字符串长度一致。
低位优先字符排序和基数排序非常的相似，假设字符串长度为W，首先以最低位W-1为键进行排序，再以W-2位为键进行排序,......，直到以0位为键进行排序，此时排序的结果就是最终的结果。低位优先字符串排序是稳定排序。
1 | public void sort(String[] a, int W){ |
5.1.3 高位优先的字符串排序
要实现一个通用的字符串排序算法（字符串的长度不一定相同），应该考虑从左向右遍历所有的字符。实现这种思想的一个很自然的方法就是一种递归算法，就是高位优先的字符串排序(MSD)。首先用键索引计数法将所有的字符串按照首字母排序，然后(递归地)再将每个首字母所对应的子数组排序（忽略首字母，因为每一类中的所有字符串的首字母都是相同的）。和快速排序一样，高位优先的字符会分为每个首字母得到一个子数组，而不是像快速排序中那样产生固定的两个或三个划分。
有个需要注意的情况就是到达字符串末尾的情况，在排序中合理的做法就是将所有的字符都已被检查过的字符串所在的子数组排在所有子数组的前面，这样就不需要递归地将该子数组排序。
1 | public class MSD { |
5.1.4 三向字符串快速排序
三向字符串快速排序根据的仍然是根据键的首字母并使用递归方法将其余部分的键排序。它特别适用于较长的含有公共前缀的字符串，并且不需要任何额外的空间。
具体的做法如下：
- 用一个字符作为中间字符，本文默认选择字符串的第一个字符作为中间字符，比它大的转移到字符串数组的末尾，比它小的转移到它的前面。
- 这样遍历之后会形成三个小组，里面的字符串开头字母分为小于中间字符，等于中间字符，大于中间字符。对分类的三个字符串数组逐一进行步骤1直到字符串中的字符全部遍历。最后形成的字符串自然有序。
1 | public class Quick3string { |
5.2 单词查找树
这里讨论的查找算法一般能够实现以下的性能：
- 查找命中所需的时间与被查找的键的长度成正比；
- 查找未命中只需查找若干字符。
和其他的树一样的，单词查找树也是由链接组成的数据结构，这些链接可能为空，也可能指向其他的结点。每个结点都只可能有一个指向它的结点，称为它的父节点，当然根结点是没有的。单词查找树一般都包含大量的空链接，因此在绘制一颗单词查找树时一般会忽略空链接。值为空的结点在符号表中没有对应的键，它的存在是为了简化单词查找树中的查找操作。
单词查找树的结构
- 单词查找树的查找操作
从根结点开始，首先经过的是键的首字母对应的链接；在下一个节点中沿着第二个字符所对应的链接继续前进；在第二个节点中沿着第三个字符对应的链接向前，这样知道达到键的最后一个字母所指向的结点或是遇到了一条空链接。这时候会出现三种情况：（1）键的尾字符对应的结点中的值非空，这是一次命中的查找，键所对应的值就是键的尾字符所对应的节点中保存的值。（2）键的尾字符所对应的结点的值为空，这是一次未命中的查找，符号表中不存在被查找的键。（3）查找结束于一条空链接，这也是一次未命中的查找。
- 单词查找树的插入操作
在插入之前要进行一次查找：在单词查找树中沿着被查找的键的所有字符到达树中表示尾字符的结点或者一个空链接。此时会出现两种情况：（1）在到达尾字符之前就遇到了一个空链接。在这种情况下，单词查找树中不存在与键的尾字符对应的节点，因此要为键中还未被检查的每个字符创建一个对应的结点并将键的值保存到最后一个字符的结点中。（2）在遇到空链接之前就到达了键的尾字符，在这种情况下，和关联数组一样，将该结点的值设置为键所对应的值。
- 结点的表示
每个节点都含有R个链接，对应着每个可能出现的字符，字符和键均隐式的保存在数据结构中。
1 | public class TrieST<Value> { |
5.2.1 三相单词查找树
为了避免R向单词查找树过度的空间消耗，使用另一种叫做三向单词查找树。在三向单词查找树中每个节点都含有一个字符、三条链接和一个值。这三条链接分别表示的是当前字母小于、等于和大于节点字母的所有键。在等价的三向单词查找树中，字符是显式地保存在结点中的，只有在沿着中间连接前进时才会根据字符找到表中的键。
1 | public class TST<Value> { |
5.3 子字符串查找
这个功能在windows中就是ctrl + F实现的功能，给定一个长度为N的文本和一段长度为M的模式字符串，在文本中找到一个和该模式相符的子字符串。
KMP算法
KMP算法的核心就是：利用匹配失败后的信息，尽量减少模式串与主串的匹配次数，以达到快速匹配的目的。
这本书中讲的有点看不太懂了。。。先来个一维数组的易于理解点的。详见[从头到尾彻底理解KMP（2014年8月22日版）_v_JULY_v的博客-CSDN博客_串的next数组怎么求]。
现在假设文本串S匹配到了i位置，模式串P匹配到了j位置：
- 如果j = -1，或者当前字符字符匹配成功，也就是S[i] == P[j]，都令i++, j++，继续匹配下一个字符；
- 如果j != -1，且当前字符匹配失败，也就是S[i] != P[j]，则令i不变，j=next[j]。此举意味着失配时，模式串P相对于文本串S右移j-next位。也就是，当匹配失败的时候，模式串向右移动的位数为：失配字符所在的位置-失配字符对应的next值，即移动的实际位数为: j-next[j]，且此值大于等于1.
这个next数组的意义就是：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。这里说的前缀就是包含首字母不包含尾字母的所有子串，后缀就是包含尾字母不包含首字母的所有子串。对于模式串aabaaf，前缀有a,aa,aab,aaba,aabaa，后缀有f,af,aaf,baaf,abaaf。[https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0028.%E5%AE%9E%E7%8E%B0strStr.md]
这个匹配的过程大概就是说，我一个一个匹配，aabaa都是能匹配上的，但是f这个位置是匹配失败的。这个时候，f前面的字符串就是aabaa，这个字符串它的最长的相同前后缀就是2，也就是aa。我们匹配失败的位置是后缀子串的后面，那么KMP要跳转的位置就是找到与其相同的前缀的后面就好了。得看图多理解几遍，这地方是为了用之前的信息来找到新的开始的匹配的地点。所以最长的前缀有利于更快的定位。
那么怎么计算前缀表呢？前缀表的意思就是说最长前缀和后缀相同的一个数值。比方说，还是上面的模式串，a的最长相同前后缀是0（因为前缀不包含最后一个字符但是必须包含首字符，后缀不包含首字符但是包含末尾字符，看的顺序还是从左到右的），aa的最长前后缀为1，aab就是0，aaba就是1，aabaa就是2，aabaaf的最长相同前后缀就是0。那么把这个前缀表当做next数组，就能够实现KMP算法。
[https://leetcode.cn/problems/implement-strstr/]这个力扣匹配字符串的代码就可以如下的写出来：
1 | class Solution{ |
字符串匹配的过程中，使用指针i来追踪文本，一个指针j来跟踪模式。《算法第四版》中使用一个数组\(dfa[][]\)来记录匹配失败时模式指针j应该回退多远。对于每个字符c，在比较了c和pattern.charAt(j)之后，\(dfa[c][j]\)表示的是应该和下个文本字符串比较的模式的位置。（也就是说要回退的位置）在查找中，\(dfa[txt.charAt(i)][j]\)是在比较了txt.charAt(i)和pat.charAt(j)之后应该和txt.charAt(i + 1)比较的位置。
一般网上的教程都是用的一维数组来表示回退，本书使用二维应该是还要实现一个查找的功能，所以把字符也给带上了。
5.4 正则表达式
正则表达式是一种强大的字符串查找程序，能够在长度为N的文本字符串中匹配长度为M的复杂模式。在最坏的情况下，它所需要的时间与MN成正比。
5.4.1 使用正则表达式的描述模式
- 连接操作：当我们写出AB时，就指定了一种语言{AB}，它含有一个由两个字符组成的字符串，由A和B连接而成。
- 或操作：可以在模式中指定多个可能的情况匹配。用|来表示这个操作，比如A|B表示的是{A,B}。连接操作的优先级高于或操作，因此AB|BCD表示的是{AB,BCD}
- 闭包操作：闭包操作可以将模式的部分重复任意的次数。模式的闭包是由将模式和自身连接任意多次而得到的所有字符串组成的语言。将标记在需要被重复的模式之后，以表示闭包。闭包的优先级高于连接操作，因此AB指定一个由A和0个或多个B字符串组成。而A*B指定由0个或多个A和一个B的字符串组成。
- 括号：改变默认的优先级顺序。
5.4.2 缩略写法
- 字符集描述符
| 名称 | 记法 | 举例 |
|---|---|---|
| 通配符 | 任意的字符 | A.B |
| 指定的集合 | 包含在[]中的字符 | [AEIOU]* |
| 范围集合 | 包含在[]中，由"."分割 | [A-Z] [0-9] |
| 补集 | 包含在[]中，首字母为"^" | [^AEIOU]* |
这里需要说明的是，^表示两种意思。
^hello会匹配hello开头的行。
[^a-z]表示的是任意一位非小写的字母。
- 闭包的简写
| 选项 | 记法 | 举例 | 原始写法 | 语言中的字符串 | 不在语言中 |
|---|---|---|---|---|---|
| 至少重复一次 | + | (AB)+ | (AB)(AB)* | AB ABABAB | ∈ BBBAAA |
| 重复0次或一次 | ? | (AB)? | ∈|AB | ∈AB | 所有其他字符串 |
| 重复指定次数 | 由{}指定次数 | (AB){3} | (AB)(AB)(AB) | ABABAB | 所有其他字符串 |
| 重复指定范围次数 | 由{}指定范围 | (AB){1-2} | (AB)|(AB)(AB) | AB ABAB | 所有其他字符串 |
- 转义序列：这些跟C语言的转义字符一样的。
5.4.3 非确定有限状态自动机
正则表达式模式匹配程序的总体结构和KMP算法的总体结构几乎相同：
- 构造和给定正则表达式相对应的非确定有限状态机
- 模拟NFA在给定文本上的运行轨迹
kleene定理：对于任意正则表达式都存在一个与之对应的非确定有限状态机，反之亦然。
NFA有着以下的特点：
- 长度为M的正则表达式中的每个字符所对应的NFA中只有一个对应的状态。NFA的起始状态为0并且含有一个虚拟的接收状态M。
- 字母表中的字符所对应的状态都有一条从它指向的边，这条边指向模式中下一个字符所对应的状态。
- 元字符"(",")","|"和"*"所对应的状态至少含有一条指出的边。（红色的）
- 有些状态有多条指出的边，但一个状态只能有一条指出的黑色边。
1 | import Chapter1.Part1_3.Bag; |
5.5 数据压缩
5.5.1 游程编码
游程编码是一种很简单的无损数据压缩算法，该算法的实现是用当前数据元素及该元素连续出现的次数来取代字符串连续出现的数据部分。例如aaaaaaaaaabbbaxxxxyyyzyx可以表示为：a10b3a1x4y3z1y1x1。但是这样的话又让出现1次的字符的长度变长了。所以当只出现1次的时候就不用带上数字了：a10b3ax4y3zyx。
这个方法的一种变种就是对位置进行计数，这样字符串就能压缩为：a0b10a13x14y18z21y22x23。
1 | public class RunLength { |
5.5.2 霍夫曼编码
霍夫曼编码是一种可变字长编码，满足前缀编码，即某个字符的编码都不能是其他字符编码的前缀编码，因此不会造成匹配的多义性。
假设要压缩go big or go home
霍夫曼编码
霍夫曼编码1
1 | public class Huffman { |
5.5.3 LZW算法
LZW算法的基础是维护一张字符串键和（定长）编码的编译表。在符号表中将128个单字符键的值初始化为8位编码，即在每个字符的7位钱添加一个0.为了简单明了，用16进制来表示编码的值，这样ASCII的A的编码即为41，R的编码为52等。将80保留为文件结束的标志并将其余的编码值(81-FF)分配给在输入中遇到的各种子字符串，即从81开始不断为新键赋予更大的编码值。为了压缩数据，只要输入还未结束，就会不断进行以下操作：
- 找出未处理的输入在符号表中最长的前缀字符串s
- 输出s的8位值
- 继续扫描s之后的一个字符c
- 在符号表中将s+c（连接s和c）的值设置为下一个编码值
比方说如果要压缩字符串ABABAB，比方说我们用2表示AB，那么就压缩为AB22，如果用0表示A，1表示B，符号流应该表示为0122。在真正的LZW压缩中，AB都是用他们的ASCII码表示。LZW初始会有一个默认的字典，包含了256个8bit字符，单个字符的记号就是它自身，也就是ASCII码了。在此基础上，编码过程中加入新的记号的映射，从256开始，称为扩展表。
那么为啥不用222表示，第一个AB也要表示为01，这就是LZW要求压缩后的编码是自解释的。即字典是不会被写入压缩文件的，在解压缩的时候，一开始字典除了默认的0->A,1->B之外并没有其他的映射，2->AB是在解压缩过程中一起加入的。
编码算法
编码器从原字符串中不断地读入新的字符，并试图将单个字符或字符串编码为记号。维护两个变量，一个P表示手头已有的，还没有被编码的字符串，一个是C表示当前新读进来的字符。
- 初始状态，字典里只有所有的默认项，例如0->a，1->b，2->c。此时P和C都是空的。
- 读入新的字符C，与P合并形成字符串P+C。
- 在字典里查找P+C，如果:
- P+C在字典里，P=P+C。
- P+C不在字典里，将P的记号输出；在字典中为P+C建立一个记号映射；更新P=C。- 返回步骤2重复，直至读完原字符串中所有字符。
核心在于第三步，P是当前维护的可以被编码为记号的子串。注意P是可以被编码为记号，但是还并未输出。新的字符C不断被读入并添加到P的尾部，只要P+C仍然能在字典中找到，就不断的增长更新\(P=P+C\)，这样就能将一个尽可能长的字符串P编码为一个记号，这就是压缩的实现。当新的P+C无法在字典中找到时，我们没有办法，输出已有的P的编码记号，并为新子串P+C建立字典表项。然后新的P从单字符C开始，重新增长，重复上述步骤。
LZW压缩1
LZW压缩2
编码过程中的3-4步，第7-8步以及8-10步，子串P发生了增长，直到新的P+C无法在字典中找到，则将当前的P输出，P则更新为新单字符C重新开始增长，输出的就是上一个P的对应的键值。
上面的编码就是0132372
解码算法
解码器的输入是压缩后的数据，即记号流。类似于编码，仍然维护两个变量pW和cW，W表示的含义是word。pW表示的是之前刚刚解码的记号，cW表示的是新读进来的记号。
- 初始状态，字典里只有所有的默认项，例如0->a，1->b，2->c。此时pW和cW都是空的。
- 读入第一个的符号cW，解码输出。注意第一个cW肯定是能直接解码的，而且一定是单个字符。
- 赋值pW=cW。
- 读入下一个符号cW。
- 在字典里查找cW，如果:
- cW在字典里：
- 解码cW，即输出 Str(cW)。
- 令P=Str(pW)，C=Str(cW)的第一个字符。
- 在字典中为P+C添加新的记号映射。
- cW不在字典里:
- 令P=Str(pW)，C=Str(pW)的第一个字符。
- 在字典中为P+C添加新的记号映射，这个新的记号一定就是cW。
- 输出P+C。
- 返回步骤3重复，直至读完所有记号。
要将上面得到的编码进行LZW解码的话，需要经过如下的步骤：
LZW解码1
LZW解码2
首先直接解码最前面的a和b，然后生成3->ab这一个映射，也就是解码器利用前面已经解出来的字符，如实的还原了编码过程中字典的生成。
6. 力扣中的典型
6.1 链表
No876. 链表的中间节点
这个有两个方法：
- 单指针法：
这需要两次遍历，首先第一遍遍历获得链表的长度len，第二遍从首指针开始移动，直到count计数器到达len / 2 + 1，然后这个值就是链表的中间节点。
1 | public ListNode middleNode(ListNode head) { |
- 双指针法：
这个需要使用快慢指针来解决，快慢指针初始都是指向链表的头部，然后慢指针每次移动一格，快指针每次移动两格，当移动到末尾的时候，慢指针指向的就是中间的位置，当跳出循环的时候，fast指针要么是指向空，要么是指向最后一个。
1 | public ListNode middleNode(ListNode head) { |
NO31. 下一个排列
下一个排列指的是，给定一个数组nums，求nums中的数字的全部排列中比nums当前组成的数字大的那些中最小的那个。
这个使用的方法是两端扫描，具体做法如下：
- 需要将一个左边的较小数和一个右边的较大数交换，以能够让当前排列变大，从而得到下一个排列。
- 同时我们需要让这个较小数尽量靠右，而较大数尽可能小。当完成交换后，较大数右边的数需要按照升序排列重新排序，这样可以保证新排列大于原来排列的情况下，使变大的幅度尽可能小。
比方说对于\([4,5,2,6,3,1]\)，我们能找到的符合条件的一对较小数与较大数为2与3，满足较小数尽量靠右，而较大数尽可能小。当我们完成交换后排列变为\([4,5,3,6,2,1]\)，此时我们可以重排较小数右边的序列，序列变为\([4,5,3,1,2,6]\)。
算法的具体描述为：
- 首先从后向前查找第一个顺序对\((i, i+ 1)\)满足\(a[i]<a[i+1]\)。这样较小数即为\(a[i]\)。此时\([i+1,n)\)必然是下降序列。
- 如果找到了顺序对，那么在区间\([i+1,n)\)中从后向前查找第一个元素j满足\(a[i]<a[j]\)，这样较大数即为\(a[j]\)
- 交换\(a[i],a[j]\)，此时可以证明区间\([i+1,n)\)必为降序。我们可以直接使用双指针反转区间\([i+1,n)\)使其变为升序，而无需对该区间进行排序。
1 | class Solution{ |