这是 数据结构和算法面试题系列第一部分，这部分主要是算法类 包括二分查找、排序算法、递归算法、随机算法、背包问题、数字问题等算法相关内容。
数据结构和算法面试题系列—二分查找算法详解
0.概述
二分查找本身是个简单的算法，但是正是因为其简单，更容易写错。甚至于在二分查找算法刚出现的时候，也是存在 bug 的（溢出的 bug），这个 bug 直到几十年后才修复（见《编程珠玑》）。本文打算对二分查找算法进行总结，并对由二分查找引申出来的问题进行分析和汇总。若有错误，请指正。
1.二分查找基础
相信大家都知道二分查找的基本算法，如下所示，这就是二分查找算法代码：
/** * 基本二分查找算法 */int binarySearch(int a[], int n, int t){ int l = 0, u = n - 1; while (l <= u) { int m = l + (u - l) / 2; // 同（l+u）/ 2，这里是为了溢出 if (t > a[m]) l = m + 1; else if (t < a[m]) u = m - 1; else return m; } return -(l+1);}复制代码算法的思想就是：从数组中间开始，每次排除一半的数据，时间复杂度为 O(lgN)。这依赖于数组有序这个性质。如果 t 存在数组中，则返回t在数组的位置；否则，不存在则返回 -(l+1)。
这里需要解释下为什么 t 不存在数组中时不是返回 -1 而要返回 -(l+1)。首先我们可以观察 l 的值，如果查找不成功，则 l 的值恰好是 t 应该在数组中插入的位置。
举个例子，假定有序数组 a={1, 3, 4, 7, 8}， 那么如果t = 0，则显然t不在数组中，则二分查找算法最终会使得l = 0 > u=-1退出循环；如果 t = 9，则 t 也不在数组中，则最后 l = 5 > u = 4 退出循环。如果 t=5，则最后l=3 > u=2退出循环。因此在一些算法中，比如DHT（一致性哈希）中，就需要这个返回值来使得新加入的节点可以插入到合适的位置中，在求最长递增子序列的 NlgN 算法中，也用到了这一点。
还有一个小点就是之所以返回 -(l+1) 而不是直接返回 -l 是因为 l 可能为 0，如果直接返回 -l 就无法判断是正常返回位置 0 还是查找不成功返回的 0。
2.查找有序数组中数字第一次出现位置
现在考虑一个稍微复杂点的问题，如果有序数组中有重复数字，比如数组 a={1, 2, 3, 3, 5, 7, 8}，需要在其中找出 3 第一次出现的位置。这里3第一次出现位置为 2。这个问题在《编程珠玑》第九章有很好的分析，这里就直接用了。算法的精髓在于循环不变式的巧妙设计，代码如下：
/** * 二分查找第一次出现位置 */int binarySearchFirst(int a[], int n, int t){ int l = -1, u = n; while (l + 1 != u) { /*循环不变式a[l]<t<=a[u] && l<u*/ int m = l + (u - l) / 2; //同（l+u）/ 2 if (t > a[m]) l = m; else u = m; } /*assert: l+1=u && a[l]<t<=a[u]*/ int p = u; if (p>=n
a[p]!=t) p = -1; return p;}复制代码算法分析：设定两个不存在的元素 a[-1]和 a[n]，使得 a[-1] < t <= a[n]，但是我们并不会去访问者两个元素，因为(l+u)/2 > l=-1, (l+u)/2 < u=n。循环不变式为l<u && t>a[l] && t<=a[u] 。循环退出时必然有 l+1=u, 而且 a[l] < t <= a[u]。循环退出后u的值为t可能出现的位置，其范围为[0, n]，如果 t 在数组中，则第一个出现的位置 p=u，如果不在，则设置 p=-1返回。该算法的效率虽然解决了更为复杂的问题，但是其效率比初始版本的二分查找还要高，因为它在每次循环中只需要比较一次，前一程序则通常需要比较两次。
举个例子：对于数组 a={1, 2, 3, 3, 5, 7, 8}，我们如果查找 t=3，则可以得到 p=u=2，如果查找 t=4，a[3]<t<=a[4]， 所以p=u=4，判断 a[4] != t，所以设置p=-1。 一种例外情况是 u>=n, 比如t=9，则 u=7，此时也是设置 p=-1.特别注意的是，l=-1，u=n 这两个值不能写成l=0，u=n-1。虽然这两个值不会访问到，但是如果改成后面的那样，就会导致二分查找失败，那样就访问不到第一个数字。如在 a={1，2，3，4，5}中查找 1，如果初始设置 l=0，u=n-1，则会导致查找失败。
扩展 如果要查找数字在数组中最后出现的位置呢？其实这跟上述算法是类似的，稍微改一下上面的算法就可以了，代码如下：
/** * 二分查找最后一次出现位置 */int binarySearchLast(int a[], int n, int t){ int l = -1, u = n; while (l + 1 != u) { /*循环不变式, a[l] <= t < a[u]*/ int m = l + (u - l) / 2; if (t >= a[m]) l = m; else u = m; } /*assert: l+1 = u && a[l] <= t < a[u]*/ int p = l; if (p<=-1
a[p]!=t) p = -1; return p;}复制代码当然还有一种方法可以将查询数字第一次出现和最后一次出现的代码写在一个程序中，只需要对原始的二分查找稍微修改即可，代码如下：
/** * 二分查找第一次和最后一次出现位置 */int binarySearchFirstAndLast(int a[], int n, int t, int firstFlag){ int l = 0; int u = n - 1; while(l <= u) { int m = l + (u - l) / 2; if(a[m] == t) { //找到了，判断是第一次出现还是最后一次出现 if(firstFlag) { //查询第一次出现的位置 if(m != 0 && a[m-1] != t) return m; else if(m == 0) return 0; else u = m - 1; } else { //查询最后一次出现的位置 if(m != n-1 && a[m+1] != t) return m; else if(m == n-1) return n-1; else l = m + 1; } } else if(a[m] < t) l = m + 1; else u = m - 1; } return -1;}复制代码3.旋转数组元素查找问题
题目
把一个有序数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转。现在给出旋转后的数组和一个数，旋转了多少位不知道，要求给出一个算法，算出给出的数在该数组中的下标，如果没有找到这个数，则返回 -1。要求查找次数不能超过 n。
分析
由题目可以知道，旋转后的数组虽然整体无序了，但是其前后两部分是部分有序的。由此还是可以使用二分查找来解决该问题的。
解1：两次二分查找
首先确定数组分割点，也就是说分割点两边的数组都有序。比如例子中的数组以位置2分割，前面部分{3,4,5}有序，后半部分{1,2}有序。然后对这两部分分别使用二分查找即可。代码如下：
/** * 旋转数组查找-两次二分查找 */int binarySearchRotateTwice(int a[], int n, int t){ int p = findRotatePosition(a, n); //找到旋转位置 if (p == -1) return binarySearchFirst(a, n, t); //如果原数组有序，则直接二分查找即可 int left = binarySearchFirst(a, p+1, t); //查找左半部分 if (left != -1) return left; //左半部分找到，则直接返回 int right = binarySearchFirst(a+p+1, n-p-1, t); //左半部分没有找到，则查找右半部分 if (right == -1) return -1; return right+p+1; //返回位置，注意要加上p+1}/** * 查找旋转位置 */int findRotatePosition(int a[], int n){ int i; for (i = 0; i < n-1; i++) { if (a[i+1] < a[i]) return i; } return -1;}复制代码解2：一次二分查找
二分查找算法有两个关键点：1）数组有序；2）根据当前区间的中间元素与t的大小关系，确定下次二分查找在前半段区间还是后半段区间进行。
仔细分析该问题，可以发现，每次根据 l 和 u 求出 m 后，m 左边（[l, m]）和右边（[m, u]）至少一个是有序的。a[m]分别与a[l]和a[u]比较，确定哪一段是有序的。
如果左边是有序的，若 t<a[m] && t>a[l], 则 u=m-1；其他情况，l =m+1；如果右边是有序的，若 t> a[m] && t<a[u] 则 l=m+1；其他情况，u =m-1； 代码如下：/** * 旋转数组二分查找-一次二分查找 */int binarySearchRotateOnce(int a[], int n, int t){ int l = 0, u = n-1; while (l <= u) { int m = l + (u-l) / 2; if (t == a[m]) return m; if (a[m] >= a[l]) { //数组左半有序 if (t >= a[l] && t < a[m]) u = m - 1; else l = m + 1; } else { //数组右半段有序 if (t > a[m] && t <= a[u]) l = m + 1; else u = m - 1; } } return -1; }复制代码数据结构和算法面试题系列—排序算法之基础排序
0.概述
排序算法也是面试中常常提及的内容，问的最多的应该是快速排序、堆排序。这些排序算法很基础，但是如果平时不怎么写代码的话，面试的时候总会出现各种 bug。虽然思想都知道，但是就是写不出来。本文打算对各种排序算法进行一个汇总，包括插入排序、冒泡排序、选择排序、计数排序、归并排序，基数排序、桶排序、快速排序等。快速排序比较重要，会单独写一篇，而堆排序见本系列的二叉堆那篇文章即可。
需要提到的一点就是：插入排序，冒泡排序，归并排序，计数排序都是稳定的排序，而其他排序则是不稳定的。
1.插入排序
插入排序是很基本的排序，特别是在数据基本有序的情况下，插入排序的性能很高，最好情况可以达到O(N)，其最坏情况和平均情况时间复杂度都是 O(N^2)。代码如下：
/** * 插入排序 */void insertSort(int a[], int n){ int i, j; for (i = 1; i < n; i++) { /* * 循环不变式：a[0...i-1]有序。每次迭代开始前，a[0...i-1]有序， * 循环结束后i=n，a[0...n-1]有序 * */ int key = a[i]; for (j = i; j > 0 && a[j-1] > key; j--) { a[j] = a[j-1]; } a[j] = key; }}复制代码2.希尔排序
希尔排序内部调用插入排序来实现，通过对 N/2，N/4...1阶分别排序，最后得到整体的有序。
/** * 希尔排序 */void shellSort(int a[], int n){ int gap; for (gap = n/2; gap > 0; gap /= 2) { int i; for (i = gap; i < n; i++) { int key = a[i], j; for (j = i; j >= gap && key < a[j-gap]; j -= gap) { a[j] = a[j-gap]; } a[j] = key; } }}复制代码3.选择排序
选择排序的思想就是第 i 次选取第 i 小的元素放在位置 i。比如第 1 次就选择最小的元素放在位置 0，第 2 次选择第二小的元素放在位置 1。选择排序最好和最坏时间复杂度都为 O(N^2)。代码如下：
/** * 选择排序 */void selectSort(int a[], int n){ int i, j, min, tmp; for (i = 0; i < n-1; i++) { min = i; for (j = i+1; j < n; j++) { if (a[j] < a[min]) min = j; } if (min != i) tmp = a[i], a[i] = a[min], a[min] = tmp; //交换a[i]和a[min] }}复制代码循环不变式：在外层循环执行前，a[0...i-1]包含 a 中最小的 i 个数，且有序。
初始时，i=0，a[0...-1] 为空，显然成立。每次执行完成后，a[0...i] 包含 a 中最小的 i+1 个数，且有序。即第一次执行完成后，a[0...0] 包含 a 最小的 1 个数，且有序。循环结束后，i=n-1，则 a[0...n-2]包含 a 最小的 n-1 个数，且已经有序。所以整个数组有序。4.冒泡排序
冒泡排序时间复杂度跟选择排序相同。其思想就是进行 n-1 趟排序，每次都是把最小的数上浮，像鱼冒泡一样。最坏情况为 O(N^2)。代码如下：
/** * 冒泡排序-经典版 */void bubbleSort(int a[], int n){ int i, j, tmp; for (i = 0; i < n; i++) { for (j = n-1; j >= i+1; j--) { if (a[j] < a[j-1]) tmp = a[j], a[j] = a[j-1], a[j-1] = tmp; } }}复制代码循环不变式：在循环开始迭代前，子数组 a[0...i-1] 包含了数组 a[0..n-1] 的 i-1 个最小值，且是排好序的。
对冒泡排序的一个改进就是在每趟排序时判断是否发生交换，如果一次交换都没有发生，则数组已经有序，可以不用继续剩下的趟数直接退出。改进后代码如下：
/** * 冒泡排序-优化版 */void betterBubbleSort(int a[], int n){ int tmp, i, j; for (i = 0; i < n; i++) { int sorted = 1; for (j = n-1; j >= i+1; j--) { if (a[j] < a[j-1]) { tmp = a[j], a[j] = a[j-1], a[j-1] = tmp; sorted = 0; } } if (sorted) return ; } }复制代码5.计数排序
假定数组为 a[0...n-1] ，数组中存在重复数字，数组中最大数字为k，建立两个辅助数组 b[] 和 c[]，b[] 用于存储排序后的结果，c[] 用于存储临时值。时间复杂度为 O(N)，适用于数字范围较小的数组。
计数排序原理如上图所示，代码如下：
/** * 计数排序 */void countingSort(int a[], int n) { int i, j; int *b = (int *)malloc(sizeof(int) * n); int k = maxOfIntArray(a, n); // 求数组最大元素 int *c = (int *)malloc(sizeof(int) * (k+1)); //辅助数组 for (i = 0; i <= k; i++) c[i] = 0; for (j = 0; j < n; j++) c[a[j]] = c[a[j]] + 1; //c[i]包含等于i的元素个数 for (i = 1; i <= k; i++) c[i] = c[i] + c[i-1]; //c[i]包含小于等于i的元素个数 for (j = n-1; j >= 0; j--) { // 赋值语句 b[c[a[j]]-1] = a[j]; //结果存在b[0...n-1]中 c[a[j]] = c[a[j]] - 1; } /*方便测试代码，这一步赋值不是必须的*/ for (i = 0; i < n; i++) { a[i] = b[i]; } free(b); free(c);}复制代码扩展： 如果代码中的给数组 b[] 赋值语句 for (j=n-1; j>=0; j--) 改为 for(j=0; j<=n-1; j++)，该代码仍然正确，只是排序不再稳定。
6.归并排序
归并排序通过分治算法，先排序好两个子数组，然后将两个子数组归并。时间复杂度为 O(NlgN）。代码如下：
/* * 归并排序-递归 * */void mergeSort(int a[], int l, int u) { if (l < u) { int m = l + (u-l)/2; mergeSort(a, l, m); mergeSort(a, m + 1, u); merge(a, l, m, u); }} /** * 归并排序合并函数 */void merge(int a[], int l, int m, int u) { int n1 = m - l + 1; int n2 = u - m; int left[n1], right[n2]; int i, j; for (i = 0; i < n1; i++) /* left holds a[l..m] */ left[i] = a[l + i]; for (j = 0; j < n2; j++) /* right holds a[m+1..u] */ right[j] = a[m + 1 + j]; i = j = 0; int k = l; while (i < n1 && j < n2) { if (left[i] < right[j]) a[k++] = left[i++]; else a[k++] = right[j++]; } while (i < n1) /* left[] is not exhausted */ a[k++] = left[i++]; while (j < n2) /* right[] is not exhausted */ a[k++] = right[j++];}复制代码扩展：归并排序的非递归实现怎么做？
归并排序的非递归实现其实是最自然的方式，先两两合并，而后再四四合并等，就是从底向上的一个过程。代码如下：
/** * 归并排序-非递归 */void mergeSortIter(int a[], int n){ int i, s=2; while (s <= n) { i = 0; while (i+s <= n){ merge(a, i, i+s/2-1, i+s-1); i += s; } //处理末尾残余部分 merge(a, i, i+s/2-1, n-1); s*=2; } //最后再从头到尾处理一遍 merge(a, 0, s/2-1, n-1);}复制代码7.基数排序、桶排序
基数排序的思想是对数字每一位分别排序（注意这里必须是稳定排序，比如计数排序等，否则会导致结果错误），最后得到整体排序。假定对 N 个数字进行排序，如果数字有 d 位，每一位可能的最大值为 K，则每一位的稳定排序需要 O(N+K) 时间，总的需要 O(d(N+K)) 时间，当 d 为常数，K=O(N) 时，总的时间复杂度为O(N)。
而桶排序则是在输入符合均匀分布时，可以以线性时间运行，桶排序的思想是把区间 [0，1) 划分成 N 个相同大小的子区间，将 N 个输入均匀分布到各个桶中，然后对各个桶的链表使用插入排序，最终依次列出所有桶的元素。
这两种排序使用场景有限，代码就略过了，更详细可以参考《算法导论》的第8章。
数据结构和算法面试题系列—排序算法之快速排序
0.概述
快速排序也是基于分治模式，类似归并排序那样，不同的是快速排序划分最后不需要merge。对一个数组 A[p..r] 进行快速排序分为三个步骤：
划分： 数组 A[p...r] 被划分为两个子数组 A[p...q-1] 和 A[q+1...r]，使得 A[p...q-1] 中每个元素都小于等于 A[q]，而 A[q+1...r] 每个元素都大于 A[q]。划分流程见下图。解决： 通过递归调用快速排序，对子数组分别排序即可。合并：因为两个子数组都已经排好序了，且已经有大小关系了，不需要做任何操作。
快速排序算法不算复杂的算法，但是实际写代码的时候却是最容易出错的代码，写的不对就容易死循环或者划分错误。
1.朴素的快速排序
这个朴素的快速排序有个缺陷就是在一些极端情况如所有元素都相等时（或者元素本身有序，如 a[] = {1,2,3,4,5}等），朴素的快速算法时间复杂度为 O(N^2)，而如果能够平衡划分数组则时间复杂度为 O(NlgN)。
/** * 快速排序-朴素版本 */void quickSort(int a[], int l, int u){ if (l >= u) return; int q = partition(a, l, u); quickSort(a, l, q-1); quickSort(a, q+1, u);}/** * 快速排序-划分函数 */int partition(int a[], int l, int u){ int i, q=l; for (i = l+1; i <= u; i++) { if (a[i] < a[l]) swapInt(a, i, ++q); } swapInt(a, l, q); return q;}复制代码2.改进-双向划分的快速排序
一种改进方法就是采用双向划分，使用两个变量 i 和 j，i 从左往右扫描，移过小元素，遇到大元素停止；j 从右往左扫描，移过大元素，遇到小元素停止。然后测试i和j是否交叉，如果交叉则停止，否则交换 i 与 j 对应的元素值。
注意，如果数组中有相同的元素，则遇到相同的元素时，我们停止扫描，并交换 i 和 j 的元素值。虽然这样交换次数增加了，但是却将所有元素相同的最坏情况由 O(N^2) 变成了差不多 O(NlgN) 的情况。比如数组 A={2,2,2,2,2}， 则使用朴素快速排序方法，每次都是划分 n 个元素为 1 个和 n-1 个，时间复杂度为 O(N^2)，而使用双向划分后，第一次划分的位置是 2，基本可以平衡划分两部分。代码如下：
/** * 快速排序-双向划分函数 */int partitionLR(int a[], int l, int u, int pivot){ int i = l; int j = u+1; while (1) { do { i++; } while (a[i] < pivot && i <= u); //注意i<=u这个判断条件，不能越界。 do { j--; } while (a[j] > pivot); if (i > j) break; swapInt(a, i, j); } // 注意这里是交换l和j，而不是l和i，因为i与j交叉后，a[i...u]都大于等于枢纽元t， // 而枢纽元又在最左边，所以不能与i交换。只能与j交换。 swapInt(a, l, j); return j;}/** * 快速排序-双向划分法 */void quickSortLR(int a[], int l, int u){ if (l >= u) return; int pivot = a[l]; int q = partitionLR(a, l, u, pivot); quickSortLR(a, l, q-1); quickSortLR(a, q+1, u);}复制代码虽然双向划分解决了所有元素相同的问题，但是对于一个已经排好序的数组还是会达到 O(N^2) 的复杂度。此外，双向划分还要注意的一点是代码中循环的写法，如果写成 while(a[i]<t) {i++;} 等形式，则当左右划分的两个值都等于枢纽元时，会导致死循环。
3.继续改进—随机法和三数取中法取枢纽元
为了解决上述问题，可以进一步改进，通过随机选取枢纽元或三数取中方式来获取枢纽元，然后进行双向划分。三数取中指的就是从数组A[l... u]中选择左中右三个值进行排序，并使用中值作为枢纽元。如数组 A[] = {1, 3, 5, 2, 4}，则我们对 A[0]、A[2]、A[4] 进行排序，选择中值 A[4](元素4) 作为枢纽元，并将其交换到 a[l] ，最后数组变成 A[] = {4 3 5 2 1}，然后跟之前一样双向排序即可。
/** * 随机选择枢纽元 */int pivotRandom(int a[], int l, int u){ int rand = randInt(l, u); swapInt(a, l, rand); // 交换枢纽元到位置l return a[l];}/** * 三数取中选择枢纽元 */int pivotMedian3(int a[], int l, int u){ int m = l + (u-l)/2; /* * 三数排序 */ if( a[l] > a[m] ) swapInt(a, l, m); if( a[l] > a[u] ) swapInt(a, l, u); if( a[m] > a[u] ) swapInt(a, m, u); /* assert: a[l] <= a[m] <= a[u] */ swapInt(a, m, l); // 交换枢纽元到位置l return a[l];}复制代码此外，在数据基本有序的情况下，使用插入排序可以得到很好的性能，而且在排序很小的子数组时，插入排序比快速排序更快，可以在数组比较小时选用插入排序，而大数组才用快速排序。
4.非递归写快速排序
非递归写快速排序着实比较少见，不过练练手总是好的。需要用到栈，注意压栈的顺序。代码如下：
/** * 快速排序-非递归版本 */void quickSortIter(int a[], int n){ Stack *stack = stackNew(n); int l = 0, u = n-1; int p = partition(a, l, u); if (p-1 > l) { //左半部分两个边界值入栈 push(stack, p-1); push(stack, l); } if (p+1 < u) { //右半部分两个边界值入栈 push(stack, u); push(stack, p+1); } while (!IS_EMPTY(stack)) { //栈不为空，则循环划分过程 l = pop(stack); u = pop(stack); p = partition(a, l, u); if (p-1 > l) { push(stack, p-1); push(stack, l); } if (p+1 < u) { push(stack, u); push(stack, p+1); } }}复制代码数据结构和算法面试题系列—随机算法总结
0.概述
随机算法涉及大量概率论知识，有时候难得去仔细看推导过程，当然能够完全了解推导的过程自然是有好处的，如果不了解推导过程，至少记住结论也是必要的。本文总结最常见的一些随机算法的题目，是几年前找工作的时候写的。需要说明的是，这里用到的随机函数 randInt(a, b) 假定它能随机的产生范围 [a,b] 内的整数，即产生每个整数的概率相等（虽然在实际中并不一定能实现，不过不要太在意，这个世界很多事情都很随机）。
1.随机排列数组
假设给定一个数组 A，它包含元素 1 到 N，我们的目标是构造这个数组的一个均匀随机排列。
一个常用的方法是为数组每个元素 A[i] 赋一个随机的优先级 P[i]，然后依据优先级对数组进行排序。比如我们的数组为 A = {1， 2， 3， 4}，如果选择的优先级数组为 P = {36， 3， 97， 19}，那么就可以得到数列 B={2, 4, 1, 3}，因为 3 的优先级最高（为97），而 2 的优先级最低（为3）。这个算法需要产生优先级数组，还需使用优先级数组对原数组排序，这里就不详细描述了，还有一种更好的方法可以得到随机排列数组。
产生随机排列数组的一个更好的方法是原地排列（in-place）给定数组，可以在 O(N) 的时间内完成。伪代码如下：
RANDOMIZE-IN-PLACE ( A , n ) for i ←1 to n do swap A[i] ↔ A[RANDOM(i , n )]复制代码如代码中所示，第 i 次迭代时，元素 A[i] 是从元素 A[i...n]中随机选取的，在第 i 次迭代后，我们就再也不会改变 A[i]。
A[i] 位于任意位置j的概率为 1/n。这个是很容易推导的，比如 A[1] 位于位置 1 的概率为 1/n，这个显然，因为 A[1] 不被1到n的元素替换的概率为 1/n，而后就不会再改变 A[1] 了。而 A[1] 位于位置 2 的概率也是 1/n，因为 A[1] 要想位于位置 2，则必须在第一次与 A[k] (k=2...n) 交换，同时第二次 A[2] 与 A[k]替换，第一次与 A[k] 交换的概率为(n-1)/n，而第二次替换概率为 1/(n-1)，所以总的概率是 (n-1)/n * 1/(n-1) = 1/n。同理可以推导其他情况。
当然这个条件只能是随机排列数组的一个必要条件，也就是说，满足元素 A[i] 位于位置 j 的概率为1/n 不一定就能说明这可以产生随机排列数组。因为它可能产生的排列数目少于 n!，尽管概率相等，但是排列数目没有达到要求，算法导论上面有一个这样的反例。
算法 RANDOMIZE-IN-PLACE可以产生均匀随机排列，它的证明过程如下：
首先给出k排列的概念，所谓 k 排列就是从n个元素中选取k个元素的排列，那么它一共有 n!/(n-k)! 个 k 排列。
循环不变式：for循环第i次迭代前，对于每个可能的i-1排列，子数组A[1...i-1]包含该i-1排列的概率为 (n-i+1)! / n!。
初始化：在第一次迭代前，i=1，则循环不变式指的是对于每个0排列，子数组A[1...i-1]包含该0排列的概率为 (n-1+1)! / n! = 1。A[1...0]为空的数组，0排列则没有任何元素，因此A包含所有可能的0排列的概率为1。不变式成立。维持：假设在第i次迭代前，数组的i-1排列出现在 A[1...i-1] 的概率为 (n-i+1) !/ n!，那么在第i次迭代后，数组的所有i排列出现在 A[1...i] 的概率为 (n-i)! / n!。下面来推导这个结论： 考虑一个特殊的 i 排列 p = {x1, x2, ... xi}，它由一个 i-1 排列 p' ={x1, x2,..., xi−1} 后面跟一个 xi 构成。设定两个事件变量E1和E2：E1为该算法将排列 p' 放置到 A[1...i-1]的事件，概率由归纳假设得知为 Pr(E1) = (n-i+1)! / n!。E2为在第 i 次迭代时将 xi 放入到 A[i] 的事件。 因此我们得到 i 排列出现在 A[1...i] 的概率为 Pr {E2 ∩ E1} = Pr {E2
E1} Pr {E1}。而Pr {E2
E1} = 1/(n − i + 1)，所以 Pr {E2 ∩ E1} = Pr {E2
E1} Pr {E1}= 1 /(n − i + 1) * (n − i + 1)! / n! = (n − i )! / n!。结束：结束的时候 i=n+1，因此可以得到 A[1...n] 是一个给定 n 排列的概率为 1/n！。C实现代码如下：
void randomInPlace(int a[], int n){ int i; for (i = 0; i < n; i++) { int rand = randInt(i, n-1); swapInt(a, i, rand); }}复制代码扩展
如果上面的随机排列算法写成下面这样，是否也能产生均匀随机排列？
PERMUTE-WITH-ALL( A , n ) for i ←1 to n do swap A[i] ↔A[RANDOM(1 , n )]复制代码注意，该算法不能产生均匀随机排列。假定 n=3，则该算法可以产生 3*3*3=27 个输出，而 3 个元素只有3!=6个不同的排列，要使得这些排列出现概率等于 1/6，则必须使得每个排列出现次数 m 满足 m/27=1/6，显然，没有这样的整数符合条件。而实际上各个排列出现的概率如下，如 {1,2,3} 出现的概率为 4/27，不等于 1/6。
排 列
概 率
<1, 2, 3>
4/27
<1, 3, 2>
5/27
<2, 1, 3>
5/27
<2, 3, 1>
5/27
<3, 1, 2>
4/27
<3, 2, 1>
4/27
2.随机选取一个数字
题： 给定一个未知长度的整数流，如何随机选取一个数？（所谓随机就是保证每个数被选取的概率相等）
解1： 如果数据流不是很长，可以存在数组中，然后再从数组中随机选取。当然题目说的是未知长度，所以如果长度很大不足以保存在内存中的话，这种解法有其局限性。
解2： 如果数据流很长的话，可以这样：
如果数据流在第1个数字后结束，那么必选第1个数字。如果数据流在第2个数字后结束，那么我们选第2个数字的概率为1/2，我们以1/2的概率用第2个数字替换前面选的随机数，得到新的随机数。......如果数据流在第n个数字后结束，那么我们选择第n个数字的概率为1/n，即我们以1/n的概率用第n个数字替换前面选的随机数，得到新的随机数。一个简单的方法就是使用随机函数 f(n)=bigrand()%n，其中 bigrand() 返回很大的随机整数，当数据流到第 n 个数时，如果 f(n)==0，则替换前面的已经选的随机数，这样可以保证每个数字被选中的概率都是 1/n。如当 n=1 时，则 f(1)=0，则选择第 1 个数，当 n=2 时，则第 2 个数被选中的概率都为 1/2，以此类推，当数字长度为 n 时，第 n 个数字被选中的概率为 1/n。代码如下(注：在 Linux/MacOS 下，rand() 函数已经可以返回一个很大的随机数了，就当做bigrand()用了)：
void randomOne(int n){ int i, select = 0; for (i = 1; i < n; i++) { int rd = rand() % n; if (rd == 0) { select = i; } } printf("%d\n", select);}复制代码3.随机选取M个数字
题： 程序输入包含两个整数 m 和 n ，其中 m<n，输出是 0~n-1 范围内的 m 个随机整数的有序列表，不允许重复。从概率角度来说，我们希望得到没有重复的有序选择，其中每个选择出现的概率相等。
解1： 先考虑个简单的例子，当 m=2，n=5 时，我们需要从 0~4 这 5 个整数中等概率的选取 2 个有序的整数，且不能重复。如果采用如下条件选取：bigrand() % 5 < 2，则我们选取 0 的概率为2/5。但是我们不能采取同样的概率来选取 1，因为选取了 0 后，我们应该以 1/4 的概率来选取 1，而在没有选取 0 的情况下，我们应该以 2/4 的概率选取 1。选取的伪代码如下：
select = mremaining = nfor i = [0, n) if (bigrand() % remaining < select) print i select-- remaining--复制代码只要满足条件 m<=n，则程序输出 m 个有序整数，不多不少。不会多选，因为每选择一个数，select--，这样当 select 减到 0 后就不会再选了。同时，也不会少选，因为每次都会remaining--，当 select/remaining=1 时，一定会选取一个数。每个子集被选择的概率是相等的，比如这里5选2则共有 C(5,2)=10 个子集，如 {0，1}，{0，2}...等，每个子集被选中的概率都是 1/10。
更一般的推导，n选m的子集数目一共有 C(n,m) 个，考虑一个特定的 m 序列，如0...m-1，则选取它的概率为m/n * (m-1)/(n-1)*....1/(n-m+1)=1/C(n,m)，可以看到概率是相等的。
Knuth 老爷爷很早就提出了这个算法，他的实现如下：
void randomMKnuth(int n, int m){ int i; for (i = 0; i < n; i++) { if ((rand() % (n-i)) < m) { printf("%d ", i); m--; } }}复制代码解2： 还可以采用前面随机排列数组的思想，先对前 m 个数字进行随机排列，然后排序这 m 个数字并输出即可。代码如下：
void randomMArray(int n, int m){ int i, j; int *x = (int *)malloc(sizeof(int) * n); for (i = 0; i < n; i++) x[i] = i; // 随机数组 for (i = 0; i < m; i++) { j = randInt(i, n-1); swapInt(x, i, j); } // 对数组前 m 个元素排序 for (i = 0; i < m; i++) { for (j = i+1; j>0 && x[j-1]>x[j]; j--) { swapInt(x, j, j-1); } } for (i = 0; i < m; i++) { printf("%d ", x[i]); } printf("\n");}复制代码4.rand7 生成 rand10 问题
题： 已知一个函数rand7()能够生成1-7的随机数，每个数概率相等，请给出一个函数rand10()，该函数能够生成 1-10 的随机数，每个数概率相等。
解1： 要产生 1-10 的随机数，我们要么执行 rand7() 两次，要么直接乘以一个数字来得到我们想要的范围值。如下面公式(1)和（2）。
idx = 7 * (rand7()-1) + rand7() ---(1) 正确idx = 8 * rand7() - 7 ---(2) 错误复制代码上面公式 (1) 能够产生 1-49 的随机数，为什么呢？因为 rand7() 的可能的值为 1-7，两个 rand7() 则可能产生 49 种组合，且正好是 1-49 这 49 个数，每个数出现的概率为 1/49，于是我们可以将大于 40 的丢弃，然后取 (idx-1) % 10 + 1 即可。公式（2）是错误的，因为它生成的数的概率不均等，而且也无法生成49个数字。
1 2 3 4 5 6 71 1 2 3 4 5 6 72 8 9 10 1 2 3 43 5 6 7 8 9 10 14 2 3 4 5 6 7 85 9 10 1 2 3 4 56 6 7 8 9 10 * *7 * * * * * * *复制代码该解法基于一种叫做拒绝采样的方法。主要思想是只要产生一个目标范围内的随机数，则直接返回。如果产生的随机数不在目标范围内，则丢弃该值，重新取样。由于目标范围内的数字被选中的概率相等，这样一个均匀的分布生成了。代码如下：
int rand7ToRand10Sample() { int row, col, idx; do { row = rand7(); col = rand7(); idx = col + (row-1)*7; } while (idx > 40); return 1 + (idx-1) % 10;}复制代码由于row范围为1-7，col范围为1-7，这样idx值范围为1-49。大于40的值被丢弃，这样剩下1-40范围内的数字，通过取模返回。下面计算一下得到一个满足1-40范围的数需要进行取样的次数的期望值：
E(# calls to rand7) = 2 * (40/49) + 4 * (9/49) * (40/49) + 6 * (9/49)2 * (40/49) + ... ∞ = ∑ 2k * (9/49)k-1 * (40/49) k=1 = (80/49) / (1 - 9/49)2 = 2.45复制代码解2： 上面的方法大概需要 2.45 次调用 rand7 函数才能得到 1 个 1-10 范围的数，下面可以进行再度优化。对于大于 40 的数，我们不必马上丢弃，可以对 41-49 的数减去 40 可得到 1-9 的随机数，而rand7可生成 1-7 的随机数，这样可以生成 1-63 的随机数。对于 1-60 我们可以直接返回，而 61-63 则丢弃，这样需要丢弃的数只有 3 个，相比前面的 9 个，效率有所提高。而对于 61-63 的数，减去60后为 1-3，rand7 产生 1-7，这样可以再度利用产生 1-21 的数，对于 1-20 我们则直接返回，对于 21 则丢弃。这时，丢弃的数就只有1个了，优化又进一步。当然这里面对rand7的调用次数也是增加了的。代码如下，优化后的期望大概是 2.2123。
int rand7ToRand10UtilizeSample() { int a, b, idx; while (1) { a = randInt(1, 7); b = randInt(1, 7); idx = b + (a-1)*7; if (idx <= 40) return 1 + (idx-1)%10; a = idx-40; b = randInt(1, 7); // get uniform dist from 1 - 63 idx = b + (a-1)*7; if (idx <= 60) return 1 + (idx-1)%10; a = idx-60; b = randInt(1, 7); // get uniform dist from 1-21 idx = b + (a-1)*7; if (idx <= 20) return 1 + (idx-1)%10; }}复制代码5.趣味概率题
1）称球问题
题： 有12个小球，其中一个是坏球。给你一架天平，需要你用最少的称次数来确定哪个小球是坏的，并且它到底是轻了还是重了。
解： 之前有总结过二分查找算法，我们知道二分法可以加快有序数组的查找。相似的，比如在数字游戏中，如果要你猜一个介于 1-64 之间的数字，用二分法在6次内肯定能猜出来。但是称球问题却不同。称球问题这里 12 个小球，坏球可能是其中任意一个，这就有 12 种可能性。而坏球可能是重了或者轻了这2种情况，于是这个问题一共有 12*2 = 24 种可能性。每次用天平称，天平可以输出的是 平衡、左重、右重 3 种可能性，即称一次可以将问题可能性缩小到原来的 1/3，则一共 24 种可能性可以在 3 次内称出来(3^3 = 27)。
为什么最直观的称法 6-6 不是最优的？在 6-6 称的时候，天平平衡的可能性是0，而最优策略应该是让天平每次称量时的概率均等，这样才能三等分答案的所有可能性。
具体怎么实施呢？ 将球编号为1-12，采用 4, 4 称的方法。
我们先将 1 2 3 4 和 5 6 7 8 进行第1次称重。如果第1次平衡，则坏球肯定在 9-12 号中。则此时只剩下 9-12 4个球，可能性为 9- 10- 11- 12- 9+ 10+ 11+ 12+ 这8种可能。接下来将 9 10 11 和 1 2 3称第2次：如果平衡，则 12 号小球为坏球，将12号小球与1号小球称第3次即可确认轻还是重。如果不平衡，则如果重了说明坏球重了，继续将9和10号球称量，重的为坏球，平衡的话则11为坏球。如果第1次不平衡，则坏球肯定在 1-8号中。则还剩下的可能性是 1+ 2+ 3+ 4+ 5- 6- 7- 8- 或者 1- 2- 3- 4- 5+ 6+ 7+ 8+，如果是1 2 3 4 这边重，则可以将 1 2 6 和 3 4 5 称，如果平衡，则必然是 7 8 轻了，再称一次7和1，便可以判断7和8哪个是坏球了。如果不平衡，假定是 1 2 6 这边重，则可以判断出 1 2 重了或者 5 轻了，为什么呢？因为如果是3+ 4+ 6-，则 1 2 3 4 比 5 6 7 8 重，但是 1 2 6 应该比 3 4 5 轻。其他情况同理，最多3次即可找出坏球。下面这个图更加清晰说明了这个原理。
2）生男生女问题
题： 在重男轻女的国家里，男女的比例是多少？在一个重男轻女的国家里，每个家庭都想生男孩，如果他们生的孩子是女孩，就再生一个，直到生下的是男孩为止。这样的国家，男女比例会是多少？
解： 还是1：1。在所有出生的第一个小孩中，男女比例是1：1；在所有出生的第二个小孩中，男女比例是1：1；.... 在所有出生的第n个小孩中，男女比例还是1：1。所以总的男女比例是1：1。
3）约会问题
题： 两人相约5点到6点在某地会面，先到者等20分钟后离去，求这两人能够会面的概率。
解： 设两人分别在5点X分和5点Y分到达目的地，则他们能够会面的条件是
X-Y
<= 20，而整个范围为 S={(x, y): 0 =< x <= 60, 0=< y <= 60}，如果画出坐标轴的话，会面的情况为坐标轴中表示的面积，概率为 (60^2 - 40^2) / 60^2 = 5/9。
4）帽子问题
题： 有n位顾客，他们每个人给餐厅的服务生一顶帽子，服务生以随机的顺序归还给顾客，请问拿到自己帽子的顾客的期望数是多少？
解： 使用指示随机变量来求解这个问题会简单些。定义一个随机变量X等于能够拿到自己帽子的顾客数目，我们要计算的是 E[X]。对于 i=1, 2 ... n，定义 Xi =I {顾客i拿到自己的帽子}，则 X=X1+X2+...Xn。由于归还帽子的顺序是随机的，所以每个顾客拿到自己帽子的概率为1/n，即 Pr(Xi=1)=1/n，从而 E(Xi)=1/n，所以E(X)=E(X1 + X2 + ...Xn)= E(X1)+E(X2)+...E(Xn)=n*1/n = 1，即大约有1个顾客可以拿到自己的帽子。
5）生日悖论
题： 一个房间至少要有多少人，才能使得有两个人的生日在同一天？
解： 对房间k个人中的每一对(i, j)定义指示器变量 Xij = {i与j生日在同一天} ，则i与j生日相同时，Xij=1，否则 Xij=0。两个人在同一天生日的概率 Pr(Xij=1)=1/n 。则用X表示同一天生日的两人对的数目，则 E(X)=E(∑ki=1∑kj=i+1Xij) = C(k,2)*1/n = k(k-1)/2n，令 k(k-1)/2n >=1，可得到 k>=28，即至少要有 28 个人，才能期望两个人的生日在同一天。
6）概率逆推问题
题： 如果在高速公路上30分钟内看到一辆车开过的几率是0.95，那么在10分钟内看到一辆车开过的几率是多少？(假设常概率条件下)
解： 假设10分钟内看到一辆车开过的概率是x，那么没有看到车开过的概率就是1-x，30分钟没有看到车开过的概率是 (1-x)^3，也就是 0.05。所以得到方程 (1-x)^3 = 0.05 ，解方程得到 x 大约是 0.63。
数据结构和算法面试题系列—递归算法总结
0.概述
前面总结了随机算法，这次再把以前写的递归算法的文章梳理一下，这篇文章主要是受到宋劲松老师写的《Linux C编程》的递归章节启发写的。最能体现算法精髓的非递归莫属了，希望这篇文章对初学递归或者对递归有困惑的朋友们能有所帮助，如有错误，也恳请各路大牛指正。二叉树的递归示例代码请参见仓库的 binary_tree 目录，本文其他代码在 这里。
1.递归算法初探
本段内容主要摘自《linux C一站式编程》，作者是宋劲松老师，这是我觉得目前看到的国内关于Linux C编程的最好的技术书籍之一，强烈推荐下！
关于递归的一个简单例子是求整数阶乘，n!=n*(n-1)!，0!=1 。则可以写出如下的递归程序：
int factorial(int n){if (n == 0)return 1;else {int recurse = factorial(n-1);int result = n * recurse;return result;}}复制代码factorial这个函数就是一个递归函数，它调用了它自己。自己直接或间接调用自己的函数称为递归函数。如果觉得迷惑，可以把 factorial(n-1) 这一步看成是在调用另一个函数－－另一个有着相同函数名和相同代码的函数，调用它就是跳到它的代码里执行，然后再返回 factorial(n-1) 这个调用的下一步继续执行。
为了证明递归算法的正确性，我们可以一步步跟进去看执行结果。记得刚学递归算法的时候，老是有丈二和尚摸不着头脑的感觉，那时候总是想着把递归一步步跟进去看执行结果。递归层次少还算好办，但是层次一多，头就大了，完全不知道自己跟到了递归的哪一层。比如求阶乘，如果只是factorial(3)跟进去问题还不大，但是若是factorial(100)要跟进去那真的会烦死人。
事实上，我们并不是每个函数都需要跟进去看执行结果的，比如我们在自己的函数中调用printf函数时，并没有钻进去看它是怎么打印的，因为我们相信它能完成打印工作。 我们在写factorial函数时有如下代码：
int recurse = factorial(n-1);int result = n * recurse;复制代码这时，如果我们相信factorial是正确的，那么传递参数为n-1它就会返回(n-1)!，那么result=n*(n-1)!=n!，从而这就是factorial(n)的结果。
当然这有点奇怪：我们还没写完factorial这个函数，凭什么要相信factorial(n-1)是正确的？如果你相信你正在写的递归函数是正确的，并调用它，然后在此基础上写完这个递归函数，那么它就会是正确的，从而值得你相信它正确。
这么说还是有点玄乎，我们从数学上严格证明一下 factorial 函数的正确性。刚才说了，factorial(n) 的正确性依赖于 factorial(n-1) 的正确性，只要后者正确，在后者的结果上乘个 n 返回这一步显然也没有疑问，那么我们的函数实现就是正确的。因此要证明factorial(n) 的正确性就是要证明 factorial(n-1) 的正确性，同理，要证明factorial(n-1) 的正确性就是要证明 factorial(n-2) 的正确性，依此类推下去，最后是：要证明 factorial(1) 的正确性就是要证明 factorial(0) 的正确性。而factorial(0) 的正确性不依赖于别的函数调用，它就是程序中的一个小的分支return 1; 这个 1 是我们根据阶乘的定义写的，肯定是正确的，因此 factorial(1) 的实现是正确的，因此 factorial(2) 也正确，依此类推，最后 factorial(n) 也是正确的。
其实这就是在中学时学的数学归纳法，用数学归纳法来证明只需要证明两点：Base Case 正确，递推关系正确。写递归函数时一定要记得写 Base Case，否则即使递推关系正确，整个函数也不正确。如果 factorial 函数漏掉了 Base Case，那么会导致无限循环。
2.递归经典问题
从上一节的一个关于求阶乘的简单例子的论述，我们可以了解到递归算法的精髓：要从功能上理解函数，同时你要相信你正在写的函数是正确的，在此基础上调用它，那么它就是正确的。 下面就从几个常见的算法题来看看如何理解递归，这是我的一些理解，欢迎大家提出更好的方法。
2.1）汉诺塔问题
题： 汉诺塔问题是个常见问题，就是说有n个大小不等的盘子放在一个塔A上面，自底向上按照从大到小的顺序排列。要求将所有n个盘子搬到另一个塔C上面，可以借助一个塔B中转，但是要满足任何时刻大盘子不能放在小盘子上面。
解： 基本思想分三步，先把上面的 N-1 个盘子经 C 移到 B，然后将最底下的盘子移到 C，再将 B 上面的N-1个盘子经 A 移动到 C。总的时间复杂度 f(n)=2f(n-1)+1，所以 f(n)=2^n-1。
/** * 汉诺塔 */void hano(char a, char b, char c, int n) { if (n <= 0) return; hano(a, c, b, n-1); move(a, c); hano(b, a, c, n-1);}void move(char a, char b){ printf("%c->%c\n", a, b);}复制代码2.2）求二叉树的深度
这里的深度指的是二叉树从根结点到叶结点最大的高度，比如只有一个结点，则深度为1，如果有N层，则高度为N。
int depth(BTNode* root) { if (root == NULL) return 0; else { int lDepth = depth(root->left); //获取左子树深度 int rDepth = depth(root->right); //获取右子树深度 return lDepth>rDepth? lDepth+1: rDepth+1; //取较大值+1即为二叉树深度 } } 复制代码那么如何从功能上理解 depth 函数呢？我们可以知道定义该函数的目的就是求二叉树深度，也就是说我们要是完成了函数 depth，那么 depth(root) 就能正确返回以 root 为根结点的二叉树的深度。因此我们的代码中 depth(root->left) 返回左子树的深度，而depth(root->right) 返回右子树的深度。尽管这个时候我们还没有写完 depth 函数，但是我们相信 depth 函数能够正确完成功能。因此我们得到了 lDepth 和rDepth，而后通过比较返回较大值加1为二叉树的深度。
如果不好理解，可以想象在 depth 中调用的函数 depth(root->left) 为另外一个同样名字完成相同功能的函数，这样就好理解了。注意 Base Case，这里就是当 root==NULL 时，则深度为0，函数返回0。
2.3）判断二叉树是否平衡
一颗平衡的二叉树是指其任意结点的左右子树深度之差不大于1。判断一棵二叉树是否是平衡的，可以使用递归算法来实现。
int isBalanceBTTop2Down(BTNode *root){ if (!root) return 1; int leftHeight = btHeight(root->left); int rightHeight = btHeight(root->right); int hDiff = abs(leftHeight - rightHeight); if (hDiff > 1) return 0; return isBalanceBTTop2Down(root->left) && isBalanceBTTop2Down(root->right);}复制代码该函数的功能定义是二叉树 root 是平衡二叉树，即它所有结点的左右子树深度之差不大于1。首先判断根结点是否满足条件，如果不满足，则直接返回 0。如果满足，则需要判断左子树和右子树是否都是平衡二叉树，若都是则返回1，否则0。
2.4）排列算法
排列算法也是递归的典范，记得当初第一次看时一层层跟代码，头都大了，现在从函数功能上来看确实好理解多了。先看代码：
/** * 输出全排列，k为起始位置，n为数组大小 */void permute(int a[], int k, int n){ if (k == n-1) { printIntArray(a, n); // 输出数组 } else { int i; for (i = k; i < n; i++) { swapInt(a, i, k); // 交换 permute(a, k+1, n); // 下一次排列 swapInt(a, i, k); // 恢复原来的序列 } }}复制代码首先明确的是 perm(a, k, n) 函数的功能:输出数组 a 从位置 k 开始的所有排列，数组长度为 n。这样我们在调用程序的时候，调用格式为 perm(a, 0, n)，即输出数组从位置 0 开始的所有排列，也就是该数组的所有排列。基础条件是 k==n-1，此时已经到达最后一个元素，一次排列已经完成，直接输出。否则，从位置k开始的每个元素都与位置k的值交换(包括自己与自己交换)，然后进行下一次排列，排列完成后记得恢复原来的序列。
假定数组a aan na a =3，则程序调用 perm(a, 0, 3) 可以如下理解： 第一次交换 0，0，并执行perm(a, 1, 3)，执行完再次交换0，0，数组此时又恢复成初始值。 第二次交换 1，0（注意数组此时是初始值），并执行perm(a, 1, 3), 执行完再次交换1，0，数组此时又恢复成初始值。 第三次交换 2，0，并执行perm(a, 1, 3)，执行完成后交换2，0，数组恢复成初始值。
也就是说，从功能上看，首先确定第0个位置，然后调用perm(a, 1, 3)输出从1开始的排列，这样就可以输出所有排列。而第0个位置可能的值为a[0], a[1],a[2]，这通过交换来保证第0个位置可能出现的值，记得每次交换后要恢复初始值。
如数组 a={1,2,3}，则程序运行输出结果为：1 2 3 ，1 3 2 ，2 1 3 ，2 3 1 ，3 2 1 ，3 1 2。即先输出以1为排列第一个值的排列，而后是2和3为第一个值的排列。
2.5）组合算法
组合算法也可以用递归实现，只是它的原理跟0-1背包问题类似。即要么选要么不选，注意不能选重复的数。完整代码如下：
/* * 组合主函数，包括选取1到n个数字 */ void combination(int a[], int n){ int *select = (int *)calloc(sizeof(int), n); // select为辅助数组，用于存储选取的数 int k; for (k = 1; k <= n; k++) { combinationUtil(a, n, 0, k, select); }}/* * 组合工具函数：从数组a从位置i开始选取k个数 */void combinationUtil(int a[], int n, int i, int k, int *select){ if (i > n) return; //位置超出数组范围直接返回，否则非法访问会出段错误 if (k == 0) { //选取完了，输出选取的数字 int j; for (j = 0; j < n; j++) { if (select[j]) printf("%d ", a[j]); } printf("\n"); } else { select[i] = 1; combinationUtil(a, n, i+1, k-1, select); //第i个数字被选取，从后续i+1开始选取k-1个数 select[i] = 0; combinationUtil(a, n, i+1, k, select); //第i个数字不选，则从后续i+1位置开始还要选取k个数 }}复制代码2.6) 逆序打印字符串
这个比较简单，代码如下：
void reversePrint(const char *str) { if (!*str) return; reversePrint(str + 1); putchar(*str);}复制代码2.7) 链表逆序
链表逆序通常我们会用迭代的方式实现，但是如果要显得特立独行一点，可以使用递归，如下，代码请见仓库的 aslist 目录。
/** * 链表逆序，递归实现。 */ListNode *listReverseRecursive(ListNode *head){ if (!head
!head->next) { return head; } ListNode *reversedHead = listReverseRecursive(head->next); head->next->next = head; head->next = NULL; return reversedHead;}复制代码数据结构和算法面试题系列—背包问题总结
0.概述
背包问题包括0-1背包问题、完全背包问题、部分背包问题等多种变种。其中，最简单的是部分背包问题，它可以采用贪心法来解决，而其他几种背包问题往往需要动态规划来求解。本文主要来源于《背包问题九讲》，我选择了比较简单的0-1背包问题和完全背包问题进行汇总。同时给出实现代码，如有错误，请各位大虾指正。本文代码在 这里。
1.部分背包问题
部分背包问题描述： 有 N 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i]，价值是 v[i]。求解将哪些物品装入背包可使价值总和最大。注意这里不要求把物品整个装入，可以只装入一个物品的部分。
解法： 部分背包问题常采用贪心算法来解决，先对每件物品计算其每单位重量价值 v[i]/w[i]，然后从具有最大单位价值的物品开始拿，然后拿第二大价值的物品，直到装满背包。按照这种贪心策略拿到的必然是价值总和最大，这个比较简单，实现代码就略去了。
2. 0-1背包问题
0-1背包问题描述
有 N 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i]，价值是v[i]。求解将哪些物品装入背包可使价值总和最大。注意物品只能要么拿要么不拿，这也正是 0-1 的意义所在。可以把部分背包问题看作是拿金粉，而 0-1 背包问题则是拿金块，一个可分，一个不可分。
分析
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即 f[i][w] 表示前 i 件物品恰放入一个容量为 c 的背包可以获得的最大价值。则其状态转移方程便是：
f[i][c] = max{f[i-1][c], f[i-1][c-w[i]]+v[i]} 复制代码这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：将前 i 件物品放入容量为 c 的背包中 这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前 i-1 件物品的问题。
如果不放第 i 件物品，那么问题就转化为 前 i-1 件物品放入容量为 v 的背包中，价值为 f[i-1][c]；如果放第i件物品，那么问题就转化为 前 i-1 件物品放入剩下的容量为 c-w[i] 的背包中，此时能获得的最大价值就是 f[i-1][c-w[i]]再加上通过放入第 i 件物品获得的价值 v[i]。优化空间复杂度
以上方法的时间和空间复杂度均为 O(CN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到 O(N)。 由于在计算 f[i][c] 的时候，我们只需要用到 f[i-1][c] 和 f[i-1][c-w[i]]，所以完全可以通过一维数组保存它们的值，这里用到的小技巧就是需要从 c=C...0 开始反推，这样就能保证在求 f[c] 的时候 f[c-w[i]] 保存的是 f[i-1][c-w[i]] 的值。注意，这里不能从 c=0...C 这样顺推，因为这样会导致 f[c-w[i]] 的值是 f[i][c-w[i]] 而不是 f[i-1][c-w[i]。这里可以优化下界，其实只需要从 c=C...w[i] 即可，可以避免不需要的计算。伪代码如下所示：
for i=0..N-1 for c=C..w[i] f[c]=max{f[c],f[c-w[i]]+v[i]};复制代码最终实现代码如下：
int knap01(int N, int C, int w[], int v[]){ int *f = (int *)calloc(sizeof(int), C+1); int i, c; for (i = 0; i < N; i++) { for (c = C; c >= w[i]; c--) { f[c] = max(f[c], f[c-w[i]] + v[i]); } printf("%d: ", i+1); printIntArray(f, C+1); // 打印f数组 } return f[C];}复制代码测试结果如下，即在背包容量为 10 的时候装第1和第2个物品(索引从0开始)，总重量为 4+5=9，最大价值为 5+6=11。
参数：w = [3, 4, 5] //物品重量列表v = [4, 5, 6] //物品价值列表C = 10结果（打印数组f，i为选择的物品索引，c为背包重。
