《数据结构与算法之美》是极客时间上的一个算法学习系列，在学习之后特在此做记录和总结。

一、递归

　　递归求解问题的分解过程，去的过程叫“递”，回来的过程叫“归”。

　　只要同时满足以下三个条件，就可以用递归来解决。

　　（1）一个问题的解可以分解为几个子问题的解。

　　（2）这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样。

　　（3）存在递归终止条件。

1）思路

　　写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。

　　对于递归代码，这种试图想清楚整个递和归过程的做法，实际上是进入了一个思维误区。很多时候，我们理解起来比较吃力，主要原因就是自己给自己制造了这种理解障碍。

　　因此，编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

2）问题

　　除了堆栈溢出、重复计算这两个常见的问题。递归代码还有很多别的问题。

　　在时间效率上，递归代码里多了很多函数调用，当这些函数调用的数量较大时，就会积聚成一个可观的时间成本。

　　在空间复杂度上，因为递归调用一次就会在内存栈中保存一次现场数据，所以在分析递归代码空间复杂度时，需要额外考虑这部分的开销。

二、排序

　　分析一个排序算法，要从几个方面入手：

　　（1）排序算法的执行效率，衡量方面：

　　　　最好情况、最坏情况、平均情况时间复杂度。

　　　　时间复杂度的系数、常数 、低阶。

　　　　比较次数和交换（或移动）次数。

　　（2）排序算法的内存消耗，针对排序算法的空间复杂度，我们还引入了一个新的概念，原地排序（Sorted in place），特指空间复杂度是 O(1) 的排序算法。

　　（3）排序算法的稳定性，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

1）冒泡排序（Bubble Sort）

　　只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。

　　有序度是数组中具有有序关系的元素对的个数。有序元素对用数学表达式表示就是这样：

有序元素对：a[i] <= a[j], 如果i < j

　　对于一个倒序排列的数组，比如 6，5，4，3，2，1，有序度是 0；对于一个完全有序的数组，比如 1，2，3，4，5，6，有序度就是 n*(n-1)/2，也就是 15。把这种完全有序的数组的有序度叫作满有序度。

　　逆序度的定义正好跟有序度相反（默认从小到大为有序），逆序度 = 满有序度 - 有序度。

　　冒泡排序包含两个操作原子，比较和交换。每交换一次，有序度就加 1。不管算法怎么改进，交换次数总是确定的，即为逆序度，也就是 n*(n-1)/2 – 初始有序度。

2）插入排序（Insertion Sort）

　　插入排序是一种原地、稳定地排序算法。它会将数组中的数据分为两个区间，已排序区间和未排序区间。

　　插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。

　　插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。

3）选择排序（Selection Sort）

　　选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。

　　但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

　　比如 5，8，5，2，9 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以就不稳定了。

4）归并排序（Merge Sort）

　　核心思想还是蛮简单的。如果要排序一个数组，先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

　　归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

　　分治是一种解决问题的处理思想，递归是一种编程技巧，这两者并不冲突。

5）快速排序（Quick Sort）

　　快排利用的也是分治思想。快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。

　　遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。

　　归并排序和快速排序的区别：

　　（1）归并排序的处理过程是由下到上的，先处理子问题，然后再合并。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。

　　（2）快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。快速排序通过设计巧妙的原地分区函数，可以实现原地排序。

6）桶排序（Bucket Sort）

　　顾名思义，会用到“桶”，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。

7）计数排序（Counting Sort）

　　计数排序其实是桶排序的一种特殊情况。

　　当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。

　　假设只有 8 个考生，分数在 0 到 5 分之间。这 8 个考生的成绩我们放在一个数组 A[8]中，它们分别是：2，5，3，0，2，3，0，3。

　　使用大小为 6 的数组 C[6]表示桶，其中下标对应分数。不过，C[6]内存储的并不是考生，而是对应的考生个数。

　　从图中可以看出，分数为 3 分的考生有 3 个，小于 3 分的考生有 4 个，所以，成绩为 3 分的考生在排序之后的有序数组 R[8]中，会保存下标 4，5，6 的位置。

8）基数排序（Radix Sort）

　　先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过 11 次排序之后，手机号码就都有序了。

　　基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。

　　除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。

9）堆排序

　　堆排序是一种原地、不稳定、时间复杂度为 O(nlogn) 的排序算法。

　　堆排序的过程大致分解成两个大的步骤，建堆和排序。

　　（1）首先将数组原地建成一个堆。所谓“原地”就是，不借助另一个数组，就在原数组上操作。

　　每个节点堆化的时间复杂度是 O(logn)，而堆排序的建堆过程的时间复杂度是 O(n)。

　　（2）建堆结束之后，数组中的数据已经是按照大顶堆的特性来组织的。

　　数组中的第一个元素就是堆顶，也就是最大的元素。把它跟最后一个元素交换，那最大元素就放到了下标为 n 的位置。

三、二分查找

　　二分查找（Binary Search）算法，也叫折半查找算法。

　　二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

1）容易出错的 3 个地方

　　（1）循环退出条件，注意是 low<=high，而不是 low。

　　（2）mid 的取值，如果 low 和 high 比较大的话，两者之和就有可能会溢出。改成 low + ((high - low) >> 1) 即可。

　　（3）low 和 high 的更新，low=mid+1，high=mid-1。注意这里的 +1 和 -1。

2）依赖条件

　　二分查找的时间复杂度是 O(logn)，查找数据的效率非常高。不过，并不是什么情况下都可以用二分查找，它的应用场景是有很大局限性的。

　　（1）二分查找依赖的是顺序表结构，简单点说就是数组。

　　（2）二分查找针对的是有序数据。

　　（3）数据量太小不适合二分查找。

　　（4）数据量太大也不适合二分查找。

3）变形问题

　　（1）查找第一个值等于给定值的元素。

　　（2）查找最后一个值等于给定值的元素。

　　（3）查找第一个大于等于给定值的元素。

　　（4）查找最后一个小于等于给定值的元素。

四、哈希算法

　　哈希算法历史悠久，业界著名的哈希算法也有很多，比如 MD5、SHA 等。

　　将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。

　　设计一个优秀的哈希算法需要满足的几点要求：

　　（1）从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）；

　　（2）对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同；

　　（3）散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；

　　（4）哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

1）应用场景

　　哈希算法的应用选了最常见的七个，分别是安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。

　　负载均衡算法有很多，比如轮询、随机、加权轮询等。也就是说，需要在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上。

　　可以通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。

五、字符串匹配

1）BF 算法

　　Brute Force的简称，中文叫作暴力匹配算法，也叫朴素匹配算法。

　　在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。把主串的长度记作 n，模式串的长度记作 m。

　　在满足性能要求的前提下，简单是首选。这也是我们常说的KISS（Keep it Simple and Stupid）设计原则。

2）RK 算法

　　全称叫 Rabin-Karp 算法，每次检查主串与子串是否匹配，需要依次比对每个字符，所以 BF 算法的时间复杂度就比较高，是 O(n*m)。

　　RK 算法的思路是这样的：通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。

　　为了提高哈希算法计算子串哈希值的效率，需要将哈希算法设计的非常有技巧。

　　比如要处理的字符串只包含 a～z 这 26 个小写字母，那我们就用二十六进制来表示一个字符串。把 a～z 这 26 个字符映射到 0～25 这 26 个数字，a 就表示 0，b 就表示 1，以此类推，z 表示 25。计算哈希的时候，只需要把进位从 10 改成 26 就可以。

3）BM 算法

　　Boyer-Moore的性能是著名的KMP 算法的 3 到 4 倍。

　　在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。

　　BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）。

4）KMP 算法

　　KMP 算法的核心思想，跟上一节讲的 BM 算法非常相近。

　　假设主串是 a，模式串是 b。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。

　　在模式串和主串匹配的过程中，把不能匹配的那个字符仍然叫作坏字符，把已经匹配的那段字符串叫作好前缀。

　　当遇到坏字符的时候，就要把模式串往后滑动，在滑动的过程中，只要模式串和好前缀有上下重合，前面几个字符的比较，就相当于拿好前缀的后缀子串，跟模式串的前缀子串在比较。

5）多模式串匹配算法

　　只需要扫描一遍主串，就能在主串中一次性查找多个模式串是否存在，从而大大提高匹配效率。

　　对敏感词字典进行预处理，构建成 Trie 树结构。

　　经典的多模式串匹配算法：AC 自动机。Trie 树跟 AC 自动机之间的关系，就像单串匹配中朴素的串匹配算法，跟 KMP 算法之间的关系一样，只不过前者针对的是多模式串而已。

　　所以，AC 自动机实际上就是在 Trie 树之上，加了类似 KMP 的 next 数组，只不过此处的 next 数组是构建在树上罢了。

六、贪心算法

　　贪心算法（greedy algorithm）有很多经典的应用，比如霍夫曼编码（Huffman Coding）、Prim 和 Kruskal 最小生成树算法、还有 Dijkstra 单源最短路径算法。

　　贪心算法解决问题的步骤：

　　（1）第一步，当看到这类问题的时候，首先要联想到贪心算法：针对一组数据，定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。

　　（2）第二步，尝试看下这个问题是否可以用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。

　　（3）第三步，举几个例子看下贪心算法产生的结果是否是最优的。

　　实际上，用贪心算法解决问题的思路，并不总能给出最优解。按照贪心思路，求出的最短路径是 S->A->E->T，路径长度是 1+4+4=9，显然不正确。

　　贪心算法的题目包括分糖果、钱币找零、区间覆盖等。

七、分治算法

　　分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

　　分治算法的递归实现中，每一层递归都会涉及这样三个操作：

　　（1）分解：将原问题分解成一系列子问题；

　　（2）解决：递归地求解各个子问题，若子问题足够小，则直接求解；

　　（3）合并：将子问题的结果合并成原问题。

　　分治算法能解决的问题，一般需要满足下面这几个条件：

　　（1）原问题与分解成的小问题具有相同的模式；

　　（2）原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别；

　　（3）具有分解终止条件，也就是说，当问题足够小时，可以直接求解；

　　（4）可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。

八、回溯算法

　　回溯算法很多时候都应用在“搜索”这类问题上。不过这里说的搜索，并不是狭义的指我们前面讲过的图的搜索算法，而是在一组可能的解中，搜索满足期望的解。

　　回溯的处理思想，有点类似枚举搜索。枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，把问题求解的过程分为多个阶段。

　　每个阶段，都会面对一个岔路口，先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

　　回溯算法的应用包括深度优先搜索、八皇后、0-1 背包问题、图的着色、旅行商问题、数独、全排列、正则表达式匹配等。

九、动态规划

　　动态规划（Dynamic Programming）比较适合用来求解最优问题，比如求最大值、最小值等等。

　　它的主要学习难点跟递归类似，那就是，求解问题的过程不太符合人类常规的思维方式。

　　把问题分解为多个阶段，每个阶段对应一个决策。记录每一个阶段可达的状态集合（去掉重复的），然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地往前推进。

1）一个模型三个特征

　　一个模型”指的是动态规划适合解决的问题的模型。这个模型定义为“多阶段决策最优解模型”。

　　“三个特征”分别是最优子结构、无后效性和重复子问题。

　　（1）最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，可以通过子问题的最优解，推导出问题的最优解。

　　（2）无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。

　　（3）重复子问题。如果用一句话概括一下，那就是，不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

2）两种思路

　　解决动态规划问题，一般有两种思路。

（1）状态转移表法

　　从左上角移动到右下角的最短路径长度为例。

　　先用简单的回溯算法解决，然后定义状态，每个状态表示一个节点，然后对应画出递归树。

　　从递归树中，很容易可以看出来，是否存在重复子问题，以及重复子问题是如何产生的。以此来寻找规律，看是否能用动态规划解决。

　　然后画出一个状态表。状态表一般都是二维的，所以你可以把它想象成二维数组。其中，每个状态包含三个变量，行、列、数组值。

　　根据决策的先后过程，从前往后递推关系，分阶段填充状态表中的每个状态。

　　思路大致为：回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码

（2）状态转移方程法

　　根据最优子结构，写出递归公式，也就是所谓的状态转移方程。

min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))

　　思路大致为：找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码