那些年，面试中常见的数据结构基础和算法题（下）
前言
這是 數據結構和算法面試題系列的下半部分，這部分主要是算法類 包括二分查找、排序算法、遞歸算法、隨機算法、背包問題、數字問題等算法相關內容。本系列完整代碼在 github 建了個倉庫，所有代碼都重新整理和做了一些基本的測試，代碼倉庫地址在這里： shishujuan/dsalg: 數據結構與算法系列匯總，如有錯誤，請在文章下面評論指出或者在 github 給我留言，我好及時改正以免誤導其他朋友。
文章末尾有系列目錄，可以按需取閱，如果需要測試，亦可以將倉庫代碼 clone 下來進行各種測試。如有錯誤或者引用不全、有侵權的地方，請大家給我指出，我好及時調整改正。如果本系列有幫助到你，也歡迎點贊或者在 github 上 star✨✨，十分感謝。
數據結構和算法面試題系列—二分查找算法詳解
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; }<span class="hljs-built_in">return</span> -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); //查找左半部分 <span class="hljs-keyword">if</span> (left != -1) <span class="hljs-built_in">return</span> left; //左半部分找到，則直接返回 int right = binarySearchFirst(a+p+1, n-p-1, t); //左半部分沒有找到，則查找右半部分 <span class="hljs-keyword">if</span> (right == -1) <span class="hljs-built_in">return</span> -1; <span class="hljs-built_in">return</span> 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)); //輔助數組<span class="hljs-keyword">for</span> (i = 0; i <= k; i++) c[i] = 0; <span class="hljs-keyword">for</span> (j = 0; j < n; j++) c[a[j]] = c[a[j]] + 1; //c[i]包含等于i的元素個數 <span class="hljs-keyword">for</span> (i = 1; i <= k; i++) c[i] = c[i] + c[i-1]; //c[i]包含小于等于i的元素個數 <span class="hljs-keyword">for</span> (j = n-1; j >= 0; j--) { // 賦值語句 b[c[a[j]]-1] = a[j]; //結果存在b[0...n-1]中 c[a[j]] = c[a[j]] - 1; } /*方便測試代碼，這一步賦值不是必須的*/ <span class="hljs-keyword">for</span> (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這個判斷條件，不能越界。<span class="hljs-keyword">do</span> { j--; } <span class="hljs-keyword">while</span> (a[j] > pivot); <span class="hljs-keyword">if</span> (i > j) <span class="hljs-built_in">break</span>; swapInt(a, i, j); } // 注意這里是交換l和j，而不是l和i，因為i與j交叉后，a[i...u]都大于等于樞紐元t， // 而樞紐元又在最左邊，所以不能與i交換。只能與j交換。 swapInt(a, l, j); <span class="hljs-built_in">return</span> 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); // 交換樞紐元到位置lreturn 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);<span class="hljs-keyword">if</span> (p-1 > l) { //左半部分兩個邊界值入棧 push(stack, p-1); push(stack, l); } <span class="hljs-keyword">if</span> (p+1 < u) { //右半部分兩個邊界值入棧 push(stack, u); push(stack, p+1); } <span class="hljs-keyword">while</span> (!IS_EMPTY(stack)) { //棧不為空，則循環劃分過程 l = pop(stack); u = pop(stack); p = partition(a, l, u); <span class="hljs-keyword">if</span> (p-1 > l) { push(stack, p-1); push(stack, l); } <span class="hljs-keyword">if</span> (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
", 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 = m
remaining = n
for 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);<span class="hljs-keyword">for</span> (i = 0; i < n; i++) x[i] = i; // 隨機數組 <span class="hljs-keyword">for</span> (i = 0; i < m; i++) { j = randInt(i, n-1); swapInt(x, i, j); } // 對數組前 m 個元素排序 <span class="hljs-keyword">for</span> (i = 0; i < m; i++) { <span class="hljs-keyword">for</span> (j = i+1; j>0 && x[j-1]>x[j]; j--) { swapInt(x, j, j-1); } } <span class="hljs-keyword">for</span> (i = 0; i < m; i++) { <span class="hljs-built_in">printf</span>(<span class="hljs-string">"%d "</span>, x[i]); } <span class="hljs-built_in">printf</span>(<span class="hljs-string">" "</span>);}
復制代碼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 7 1 1 2 3 4 5 6 7 2 8 9 10 1 2 3 4 3 5 6 7 8 9 10 1 4 2 3 4 5 6 7 8 5 9 10 1 2 3 4 5 6 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);<span class="hljs-built_in">return</span> 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-124個球，可能性為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
", 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); <span class="hljs-keyword">if</span> (hDiff > 1) <span class="hljs-built_in">return</span> 0; <span class="hljs-built_in">return</span> 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(" ");
} 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; <span class="hljs-built_in">return</span> 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;<span class="hljs-keyword">for</span> (i = 0; i < N; i++) { <span class="hljs-keyword">for</span> (c = C; c >= w[i]; c--) { f[c] = max(f[c], f[c-w[i]] + v[i]); } <span class="hljs-built_in">printf</span>(<span class="hljs-string">"%d: "</span>, i+1); <span class="hljs-built_in">print</span>IntArray(f, C+1); // 打印f數組 } <span class="hljs-built_in">return</span> 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為背包重量，值為背包物品價值）： i/c 0 1 2 3 4 5 6 7 8 9 10 0: 0 0 0 4 4 4 4 4 4 4 4 1: 0 0 0 4 5 5 5 9 9 9 9 2: 0 0 0 4 5 6 6 9 10 11 11 KNap01 max: 11 復制代碼初始化的細節問題
我們看到的求最優解的背包問題題目中，事實上有兩種不太相同的問法。有的題目要求“恰好裝滿背包”時的最優解，有的題目則并沒有要求必須把背包裝滿。一種區別這兩種問法的實現方法是在初始化的時候有所不同。
如果是第一種問法，要求恰好裝滿背包，那么在初始化時除了 f[0] 為 0 其它
f[1..C]均設為-∞，這樣就可以保證最終得到的 f[N] 是一種恰好裝滿背包的最優解。如果并沒有要求必須把背包裝滿，而是只希望價格盡量大，初始化時應該將f[0..C]全部設為0。為什么呢？可以這樣理解：初始化的 f 數組事實上就是在沒有任何物品可以放入背包時的合法狀態。如果要求背包恰好裝滿，那么此時只有容量為 0 的背包可能被價值為 0 的東西 “恰好裝滿”，其它容量的背包均沒有合法的解，屬于未定義的狀態，它們的值就都應該是 -∞ 了。如果背包并非必須被裝滿，那么任何容量的背包都有一個合法解“什么都不裝”，這個解的價值為0，所以初始時狀態的值也就全部為0了。
3.完全背包問題
問題描述
有 N 種物品和一個容量為 C 的背包，每種物品都有無限件可用。第i種物品的重量是 w[i]，價值是v[i]。求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量，且價值總和最大，物品不能只裝部分。
基本思路
這個問題非常類似于0-1背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關的策略已并非取或不取兩種，而是有取0件、取1件、取2件...等很多種。如果仍然按照解01背包時的思路，令 f[i][c] 表示前 i 種物品恰放入一個容量為 c 的背包的最大權值。仍然可以按照每種物品不同的策略寫出狀態轉移方程，像這樣：
f[i][c] = max{f[i-1][c-k*w[i]]+ k*w[i]| 0<=k*w[i]<=c } 復制代碼這跟0-1背包問題一樣有O(CN)個狀態需要求解，但求解每個狀態的時間已經不是常數了，求解狀態
f[i][c]的時間是O(c/w[i])，總的復雜度可以認為是O(CN*Σ(c/w[i]))，是比較大的。實現代碼如下：/* * 完全背包問題 */ int knapComplete(int N, int C, int w[], int v[]) { int *f = (int *)calloc(sizeof(int), C+1); int i, c, k; for (i = 0; i < N; i++) { for (c = C; c >= 0; c--) { for (k = 0; k <= c/w[i]; k++) { f[c] = max(f[c], f[c-k*w[i]] + k*v[i]); } } printf("%d: ", i+1); printIntArray(f, C+1); } return f[C]; } 復制代碼使用與0-1背包問題相同的例子，運行程序結果如下，最大價值為 13，即選取 2個重量3，1個重量4的物品，總價值最高，為
4*2 + 5 = 13。i/c: 0 1 2 3 4 5 6 7 8 9 10 0: 0 0 0 4 4 4 8 8 8 12 12 1: 0 0 0 4 5 5 8 9 10 12 13 2: 0 0 0 4 5 6 8 9 10 12 13KNapComplete max: 13
復制代碼轉換為0-1背包問題
既然01背包問題是最基本的背包問題，那么我們可以考慮把完全背包問題轉化為01背包問題來解。最簡單的想法是，考慮到第i種物品最多選
C/w[i]件，于是可以把第 i 種物品轉化為C/w[i]件費用及價值均不變的物品，然后求解這個01背包問題。這樣完全沒有改進基本思路的時間復雜度，但這畢竟給了我們將完全背包問題轉化為01背包問題的思路：將一種物品拆成多件物品。更高效的轉化方法是：把第 i 種物品拆成重量為
w[i]*2^k、價值為w[i]*2^k的若干件物品，其中 k 滿足w[i]*2^k<=C。這是二進制的思想，因為不管最優策略選幾件第 i 種物品，總可以表示成若干個2^k件物品的和。這樣把每種物品拆成O(log C/w[i])件物品，是一個很大的改進。但我們有更優的O(CN)的算法。進一步優化—O(CN)解法
我們可以采用與0-1背包問題相反的順序遍歷，從而可以得到 O(CN) 的解法，偽代碼如下：
for i=0..N-1 for c=w[i]..C f[c]=max{f[c],f[c-w[i]]+v[i]}; 復制代碼這個偽代碼與0-1背包偽代碼只是 C 的循環次序不同而已。0-1背包之所以要按照
v=V..0的逆序來循環。這是因為要保證第i次循環中的狀態f[i][c]是由狀態f[i-1][c-w[i]]遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時，依據的是一個絕無已經選入第i件物品的子結果f[i-1][c-w[i]]。而現在完全背包的特點恰是每種物品可選無限件，所以在考慮“加選一件第i種物品”這種策略時，卻正需要一個可能已選入第i種物品的子結果f[i][c-w[i]]，所以就可以并且必須采用c=w[i]..C的順序循環。這就是這個簡單的程序為何成立的道理。實現代碼如下：/** * 完全背包問題-仿01背包解法 */ int knapCompleteLike01(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 = w[i]; c <= C; c++) { f[c] = max(f[c], f[c-w[i]] + v[i]); } printf("%d: ", i+1); printIntArray(f, C+1);} <span class="hljs-built_in">return</span> f[C];}
復制代碼數據結構和算法面試題系列—數字題總結
0.概述
數學是科學之基礎，數字題往往也是被面試玩出花來。數學本身是有趣味的一門學科，前段時間有點不務正業，對數學產生了濃厚的興趣，于是看了幾本數學史論的書，也買了《幾何原本》和《陶哲軒的實分析》，看了部分章節，受益良多，有興趣的朋友可以看看。特別是幾何原本，歐幾里得上千年前的著作，里面的思考和證明方式真的富有啟發性，老少咸宜。本文先總結下面試題中的數字題，我盡量增加了一些數學方面的證明，如有錯誤，也請指正。本文代碼都在 這里。
1.找質數問題
題： 寫一個程序，找出前N個質數。比如N為100，則找出前100個質數。
分析： 質數(或者叫素數)指在大于1的自然數中，除了1和該數自身外，無法被其他自然數整除的數，如
2，3，5...。最基本的想法就是對 1 到 N 的每個數進行判斷，如果是質數則輸出。一種改進的方法是不需要對 1 到 N 所有的數都進行判斷，因為除了 2 外的偶數肯定不是質數，而奇數可能是質數，可能不是。然后我們可以跳過2與3的倍數，即對于6n，6n+1, 6n+2, 6n+3, 6n+4, 6n+5，我們只需要判斷6n+1與6n+5是否是質數即可。判斷某個數m是否是質數，最基本的方法就是對 2 到 m-1 之間的數整除 m，如果有一個數能夠整除 m，則 m 就不是質數。判斷 m 是否是質數還可以進一步改進，不需要對 2 到 m-1 之間的數全部整除 m，只需要對 2 到 根號m 之間的數整除m就可以。如用
2，3，4，5...根號m整除 m。其實這還是有浪費，因為如果2不能整除，則2的倍數也不能整除，同理3不能整除則3的倍數也不能整除，因此可以只用2到根號m之間小于根號m的質數去除即可。解： 預先可得2，3，5為質數，然后跳過2與3的倍數，從7開始，然后判斷11，然后判斷13，再是17...規律就是從5加2，然后加4，然后加2，然后再加4。如此反復即可，如下圖所示，只需要判斷
7，11，13，17，19，23，25，29...這些數字。判斷是否是質數采用改進后的方案，即對2到根號m之間的數整除m來進行判斷。需要注意一點，不能直接用根號m判斷，因為對于某些數字，比如 121 開根號可能是 10.999999，所以最好使用乘法判斷，如代碼中所示。
/** * 找出前N個質數, N > 3 */ int primeGeneration(int n) { int *prime = (int *)malloc(sizeof(int) * n); int gap = 2; int count = 3; int maybePrime = 5; int i, isPrime;/* 注意：2, 3, 5 是質數 */ prime[0] = 2; prime[1] = 3; prime[2] = 5; <span class="hljs-keyword">while</span> (count < n) { maybePrime += gap; gap = 6 - gap; isPrime = 1; <span class="hljs-keyword">for</span> (i = 2; prime[i]*prime[i] <= maybePrime && isPrime; i++) <span class="hljs-keyword">if</span> (maybePrime % prime[i] == 0) isPrime = 0; <span class="hljs-keyword">if</span> (isPrime) prime[count++] = maybePrime; } <span class="hljs-built_in">printf</span>(<span class="hljs-string">" First %d Prime Numbers are : "</span>, count); <span class="hljs-keyword">for</span> (i = 0; i < count; i++) { <span class="hljs-keyword">if</span> (i % 10 == 0) <span class="hljs-built_in">printf</span>(<span class="hljs-string">" "</span>); <span class="hljs-built_in">printf</span>(<span class="hljs-string">"%5d"</span>, prime[i]); } <span class="hljs-built_in">printf</span>(<span class="hljs-string">" "</span>); <span class="hljs-built_in">return</span> 0;}
復制代碼2.階乘末尾含0問題
題： 給定一個整數N，那么N的階乘N！末尾有多少個0呢？（該題取自《編程之美》）
解1： 流行的解法是，如果 N！= K10M，且K不能被10整除，則 N！末尾有 M 個0。考慮 N！可以進行質因數分解，N！= (2X) * (3Y) * (5Z)..., 則由于10 = 25，所以0的個數只與
X和Z相關，每一對2和5相乘得到一個 10，所以 0 的個數M = min(X， Z)，顯然 2 出現的數目比 5 要多，所以 0 的個數就是 5 出現的個數。由此可以寫出如下代碼：/** * N!末尾0的個數 */ int numOfZero(int n) { int cnt = 0, i, j; for (i = 1; i <= n; i++) { j = i; while (j % 5 == 0) { cnt++; j /= 5; } } return cnt; } 復制代碼解2： 繼續分析可以改進上面的代碼，為求出1到N的因式分解中有多少個5，令 Z=N/5 + N/(52) + N/(53)+... 即 N/5 表示 1 到 N 的數中 5 的倍數貢獻一個 5，N/(52) 表示 52 的倍數再貢獻一個 5...。舉個簡單的例子，比如求1到100的數因式分解中有多少個5，可以知道5的倍數有20個，25的倍數有4個，所以一共有24個5。代碼如下：
/** * N!末尾0的個數-優化版 */ int numOfZero2(int n) { int cnt = 0; while (n) { cnt += n/5; n /= 5; } return cnt; } 復制代碼總結： 上面的分析乏善可陳，不過需要提到的一點就是其中涉及到的一條算術基本定理，也就是 任意大于1的自然數都可以分解為質數的乘積，而且該分解方式是唯一的。 定理證明分為兩個部分，存在性和唯一性。證明如下：
存在性證明
使用反證法來證明，假設存在大于1的自然數不能寫成質數的乘積，把最小的那個稱為n。自然數可以根據其可除性（是否能表示成兩個不是自身的自然數的乘積）分成3類：質數、合數和1。
首先，按照定義，n大于1。
其次，n 不是質數，因為質數p可以寫成質數乘積：p=p，這與假設不相符合。因此n只能是合數，但每個合數都可以分解成兩個嚴格小于自身而大于1的自然數的積。設n = a*b，a 和 b都是大于1小于n的數，由假設可知，a和b都可以分解為質數的乘積，因此n也可以分解為質數的乘積，所以這與假設矛盾。由此證明所有大于1的自然數都能分解為質數的乘積。唯一性證明
當n=1的時候，確實只有一種分解。
假設對于自然數 n>1，存在兩種因式分解: n=p1...pm
= q1...qk，p1<=...<=pm， q1<=...<=qk，其中 p 和 q 都是質數，我們要證明 p1=q1，p2=q2...如果不相等，我們可以設 p1 < q1，從而 p1 小于所有的 q。由于 p1 和 q1 是質數，所以它們的最大公約數為1，由歐幾里德算法可知存在整數 a 和 b 使得 a * p1 + b * q1 = 1。因此
a * p1 * q2...qk + b * q1 * q2...qk = q2...qk (等式1)。由于 q1...qk = n，因此等式1左邊是 p1 的整數倍，從而等式1右邊的 q2...qk 也必須是 p1 的整數倍，因此必然有 p1 = qi，i > 1。而這與前面 p1 小于所有的 q 矛盾，因此，由對稱性，對 p1 > q1 這種情況可以得到類似結論，故可以證明 p1 = q1，同理可得 p2 = q2...pm=qk，由此完成唯一性的證明。3.1-N正整數中1的數目
題： 給定一個十進制正整數N，求出從 1 到 N 的所有整數中包含 1 的個數。比如給定 N=23，則包含1的個數為13。其中個位出現1的數字有 1，11，21，共3個，十位出現1的數字有 10，11...19 共10個，所以總共包含 1 的個數為
3 + 10 = 13個。分析： 最自然的想法莫過于直接遍歷1到N，求出每個數中包含的1的個數，然后將這些個數相加就是總的 1 的個數。需要遍歷 N 個數，每次計算 1 的個數需要 O(log10N)，該算法復雜度為 O(Nlog10N)。當數字N很大的時候，該算法會耗費很長的時間，應該還有更好的方法。
解： 我們可以從1位數開始分析，慢慢找尋規律。
當 N 為 1 位數時，對于 N>=1，1 的個數 f(N) 為1。
當 N 為 2 位數時，則個位上1的個數不僅與個位數有關，還和十位數字有關。
當 N=23 時，個位上 1 的個數有 1、11、21 共3個，十位上1的個數為 10，11...19 共10個，所以 1 的個數
f(N) = 3+10 = 13。如果 N 的個位數 >=1，則個位出現1的次數為十位數的數字加1；如果 N 的個位數為0，則個位出現 1 的次數等于十位數的數字。
十位數上出現1的次數類似，如果N的十位數字等于1，則十位數上出現1的次數為各位數字加1；如果N的十位數字大于1，則十位數上出現1的次數為10。當 N 為 3 位數時，同樣分析可得1的個數。如 N=123，可得
1出現次數 = 13+20+24 = 57。當 N 為 4,5...K 位數時，我們假設
N=abcde，則要計算百位上出現1的數目，則它受到三個因素影響：百位上的數字，百位以下的數字，百位以上的數字。如果百位上數字為0，則百位上出現1的次數為更高位數字決定。如 N=12013，則百位出現1的數字有100~199， 1000~1199， 2100~2199...11100~111999 共 1200 個，等于百位的更高位數字(12)*當前位數(100)。
如果百位上數字為1，則百位上出現1的次數不僅受更高位影響，還受低位影響。如12113，則百位出現1的情況共有 1200+114=1314 個，也就是高位影響的 12 * 100 + 低位影響的 113+1 = 114 個。
如果百位上數字為其他數字，則百位上出現1的次數僅由更高位決定。如 12213，則百位出現1的情況為 (12+1)*100=1300。有以上分析思路，寫出下面的代碼。其中 low 表示低位數字，curr 表示當前考慮位的數字，high 表示高位數字。一個簡單的分析，考慮數字 123，則首先考慮個位，則 curr 為 3，低位為 0，高位為 12；然后考慮十位，此時 curr 為 2，低位為 3，高位為 1。其他的數字可以以此類推，實現代碼如下：
/** * 1-N正整數中1的個數 */ int numOfOne(int n) { int factor = 1, cnt = 0; //factor為乘數因子 int low = 0, curr = 0, high = 0; while (n / factor != 0) { low = n - n/factor * factor; //low為低位數字，curr為當前考慮位的數字，high為高位數字 curr = n/factor % 10; high = n/(factor * 10);switch(curr) { <span class="hljs-keyword">case</span> 0: //當前位為0的情況 cnt += high * factor; <span class="hljs-built_in">break</span>; <span class="hljs-keyword">case</span> 1: //當前位為1的情況 cnt += high * factor + low + 1; <span class="hljs-built_in">break</span>; default: //當前位為其他數字的情況 cnt += (high+1) * factor; <span class="hljs-built_in">break</span>; } factor *= 10; } <span class="hljs-built_in">return</span> cnt;}
復制代碼4.和為N的正整數序列
題： 輸入一個正整數數N，輸出所有和為N連續正整數序列。例如輸入 15，由于
1+2+3+4+5=4+5+6=7+8=15，所以輸出 3 個連續序列 1-5、4-6和7-8。解1：運用數學規律
假定有 k 個連續的正整數和為 N，其中連續序列的第一個數為 x，則有
x+(x+1)+(x+2)+...+(x+k-1) = N。從而可以求得x = (N - k*(k-1)/2) / k。當x<=0時，則說明已經沒有正整數序列的和為 N 了，此時循環退出。初始化 k=2，表示2個連續的正整數和為 N，則可以求出 x 的值，并判斷從 x 開始是否存在2個連續正整數和為 N，若不存在則 k++，繼續循環。/** * 查找和為N的連續序列 */ int findContinuousSequence(int n) { int found = 0; int k = 2, x, m, i; // k為連續序列的數字的數目，x為起始的值，m用于判斷是否有滿足條件的值。 while (1) { x = (n - k*(k-1)/2) / k; // 求出k個連續正整數和為n的起始值x m = (n - k*(k-1)/2) % k; // m用于判斷是否有滿足條件的連續正整數值<span class="hljs-keyword">if</span> (x <= 0) <span class="hljs-built_in">break</span>; // 退出條件，如果x<=0，則循環退出。 <span class="hljs-keyword">if</span> (!m) { // m為0，表示找到了連續子序列和為n。 found = 1; <span class="hljs-built_in">print</span>ContinuousSequence(x, k); } k++; } <span class="hljs-built_in">return</span> found;}
/**
打印連續子序列
*/
void printContinuousSequence(int x, int k)
{
int i;
for (i = 0; i < k; i++) {
printf("%d ", x++);
}
printf("
");
}
復制代碼解2：序列結尾位置法
因為序列至少有兩個數，可以先判定以數字2結束的連續序列和是否有等于 n 的，然后是以3結束的連續序列和是否有等于 n 的，...以此類推。此解法思路參考的何海濤先生的博文，代碼如下：
/** * 查找和為N的連續序列-序列結尾位置法 */ int findContinuousSequenceEndIndex(int n) { if (n < 3) return 0;int found = 0; int begin = 1, end = 2; int mid = (1 + n) / 2; int sum = begin + end; <span class="hljs-keyword">while</span> (begin < mid) { <span class="hljs-keyword">if</span> (sum > n) { sum -= begin; begin++; } <span class="hljs-keyword">else</span> { <span class="hljs-keyword">if</span> (sum == n) { found = 1; <span class="hljs-built_in">print</span>ContinuousSequence(begin, end-begin+1); } end++; sum += end; } } <span class="hljs-built_in">return</span> found;}
復制代碼擴展： 是不是所有的正整數都能分解為連續正整數序列呢？
答案： 不是。并不是所有的正整數都能分解為連續的正整數和，如 32 就不能分解為連續正整數和。對于奇數，我們總是能寫成
2k+1的形式，因此可以分解為[k,k+1]，所以總是能分解成連續正整數序列。對于每一個偶數，均可以分解為質因數之積，即 n = 2i * 3j * 5k...，如果除了i之外，j，k...均為0，那么 n = 2i，對于這種數，其所有的因數均為偶數，是不存在連續子序列和為 n 的，因此除了2的冪之外的所有n>=3的正整數均可以寫成一個連續的自然數之和。5.最大連續子序列和
題： 求取數組中最大連續子序列和，例如給定數組為
A = {1， 3， -2， 4， -5}， 則最大連續子序列和為 6，即1 + 3 +（-2）+ 4 = 6。分析： 最大連續子序列和問題是個很老的面試題了，最佳的解法是
O(N)復雜度，當然有些值得注意的地方。這里總結三種常見的解法，重點關注最后一種O(N)的解法即可。需要注意的是有些題目中的最大連續子序列和如果為負，則返回0；而本題如果是全為負數，則返回最大的負數即可。解1： 因為最大連續子序列和只可能從數組 0 到 n-1 中某個位置開始，我們可以遍歷 0 到 n-1 個位置，計算由這個位置開始的所有連續子序列和中的最大值。最終求出最大值即可。
/** * 最大連續子序列和 */ int maxSumOfContinuousSequence(int a[], int n) { int max = a[0], i, j, sum; // 初始化最大值為第一個元素 for (i = 0; i < n; i++) { sum = 0; // sum必須清零 for (j = i; j < n; j++) { //從位置i開始計算從i開始的最大連續子序列和的大小，如果大于max，則更新max。 sum += a[j]; if (sum > max) max = sum; } } return max; } 復制代碼解2： 該問題還可以通過分治法來求解，最大連續子序列和要么出現在數組左半部分，要么出現在數組右半部分，要么橫跨左右兩半部分。因此求出這三種情況下的最大值就可以得到最大連續子序列和。
/** * 最大連續子序列和-分治法 */ int maxSumOfContinuousSequenceSub(int a[], int l, int u) { if (l > u) return 0; if (l == u) return a[l]; int m = (l + u) / 2;/*求橫跨左右的最大連續子序列左半部分*/ int lmax = a[m], lsum = 0; int i; <span class="hljs-keyword">for</span> (i = m; i >= l; i--) { lsum += a[i]; <span class="hljs-keyword">if</span> (lsum > lmax) lmax = lsum; } /*求橫跨左右的最大連續子序列右半部分*/ int rmax=a[m+1], rsum = 0; <span class="hljs-keyword">for</span> (i = m+1; i <= u; i++) { rsum += a[i]; <span class="hljs-keyword">if</span> (rsum > rmax) rmax = rsum; } <span class="hljs-built_in">return</span> max3(lmax+rmax, maxSumOfContinuousSequenceSub(a, l, m), maxSumOfContinuousSequenceSub(a, m+1, u)); //返回三者最大值}
復制代碼解3： 還有一種更好的解法，只需要
O(N)的時間。因為最大 連續子序列和只可能是以位置0～n-1中某個位置結尾。當遍歷到第 i 個元素時，判斷在它前面的連續子序列和是否大于0，如果大于0，則以位置 i 結尾的最大連續子序列和為元素 i 和前面的連續子序列和相加；否則，則以位置 i 結尾最大連續子序列和為a[i]。/** * 最打連續子序列和-結束位置法 */ int maxSumOfContinuousSequenceEndIndex(int a[], int n) { int maxSum, maxHere, i; maxSum = maxHere = a[0]; // 初始化最大和為a[0] for (i = 1; i < n; i++) { if (maxHere <= 0) maxHere = a[i]; // 如果前面位置最大連續子序列和小于等于0，則以當前位置i結尾的最大連續子序列和為a[i] else maxHere += a[i]; // 如果前面位置最大連續子序列和大于0，則以當前位置i結尾的最大連續子序列和為它們兩者之和 if (maxHere > maxSum) { maxSum = maxHere; //更新最大連續子序列和 } } return maxSum; } 復制代碼6.最大連續子序列乘積
題： 給定一個整數序列（可能有正數，0和負數），求它的一個最大連續子序列乘積。比如給定數組
a[] = {3, -4, -5, 6, -2}，則最大連續子序列乘積為 360，即3*(-4)*(-5)*6=360。解： 求最大連續子序列乘積與最大連續子序列和問題有所不同，因為其中有正有負還有可能有0，可以直接利用動歸來求解，考慮到可能存在負數的情況，我們用 max[i] 來表示以 a[i] 結尾的最大連續子序列的乘積值，用 min[i] 表示以 a[i] 結尾的最小的連續子序列的乘積值，那么狀態轉移方程為：
max[i] = max{a[i], max[i-1]*a[i], min[i-1]*a[i]}; min[i] = min{a[i], max[i-1]*a[i], min[i-1]*a[i]}; 復制代碼初始狀態為
max[0] = min[0] = a[0]。代碼如下：/** * 最大連續子序列乘積 */ int maxMultipleOfContinuousSequence(int a[], int n) { int minSofar, maxSofar, max, i; int maxHere, minHere; max = minSofar = maxSofar = a[0];<span class="hljs-keyword">for</span>(i = 1; i < n; i++){ int maxHere = max3(maxSofar*a[i], minSofar*a[i], a[i]); int minHere = min3(maxSofar*a[i], minSofar*a[i], a[i]); maxSofar = maxHere, minSofar = minHere; <span class="hljs-keyword">if</span>(max < maxSofar) max = maxSofar; } <span class="hljs-built_in">return</span> max;}
復制代碼7.比特位相關
1) 判斷一個正整數是否是2的整數次冪
題： 給定一個正整數 n，判斷該正整數是否是 2 的整數次冪。
解1： 一個基本的解法是設定
i=1開始，循環乘以2直到i>=n，然后判斷 i 是否等于 n 即可。解2： 還有一個更好的方法，那就是觀察數字的二進制表示，如
n=101000，則我們可以發現n-1=100111。也就是說n -> n-1是將 n 最右邊的 1 變成了 0，同時將 n 最右邊的 1 右邊的所有比特位由0變成了1。因此如果n & (n-1) == 0就可以判定正整數 n 為 2的整數次冪。/** * 判斷正整數是2的冪次 */ int powOf2(int n) { assert(n > 0); return !(n & (n-1)); } 復制代碼2) 求一個整數二進制表示中1的個數
題： 求整數二進制表示中1的個數，如給定 N=6，它的二進制表示為 0110，二進制表示中1的個數為2。
解1： 一個自然的方法是將N和1按位與，然后將N除以2，直到N為0為止。該算法代碼如下：
int numOfBit1(int n) { int cnt = 0; while (n) { if (n & 1) ++cnt; n >>= 1; } return cnt; } 復制代碼上面的代碼存在一個問題，如果輸入為負數的話，會導致死循環，為了解決負數的問題，如果使用的是JAVA，可以直接使用無符號右移操作符 >>> 來解決，如果是在C/C++里面，為了避免死循環，我們可以不右移輸入的數字i。首先
i & 1，判斷i的最低位是不是為1。接著把1左移一位得到2，再和i做與運算，就能判斷i的次高位是不是1...，這樣反復左移，每次都能判斷i的其中一位是不是1。/** * 二進制表示中1的個數-解法1 */ int numOfBit1(int n) { int cnt = 0; unsigned int flag = 1; while (flag) { if(n & flag) cnt++;flag = flag << 1; <span class="hljs-keyword">if</span> (flag > n) <span class="hljs-built_in">break</span>; } <span class="hljs-built_in">return</span> cnt;}
復制代碼解2： 一個更好的解法是采用第一個題中類似的思路，每次
n&(n-1)就能把n中最右邊的1變為0，所以很容易求的1的總數目。/** * 二進制表示中1的個數-解法2 */ int numOfBit1WithCheck(int n) { int cnt = 0; while (n != 0) { n = (n & (n-1)); cnt++; } return cnt; } 復制代碼3) 反轉一個無符號整數的所有比特位
題： 給定一個無符號整數N，反轉該整數的所有比特位。例如有一個 8 位的數字
01101001，則反轉后變成10010110，32 位的無符號整數的反轉與之類似。解1： 自然的解法就是參照字符串反轉的算法，假設無符號整數有n位，先將第0位和第n位交換，然后是第1位和第n-1位交換...注意一點就是交換兩個位是可以通過異或操作 XOR 來實現的，因為
0 XOR 0 = 0,1 XOR 1 = 0,0 XOR 1 = 1,1 XOR 0 = 1，使用 1 異或 0/1 會讓其值反轉。/** * 反轉比特位 */ uint swapBits(uint x, uint i, uint j) { uint lo = ((x >> i) & 1); // 取x的第i位的值 uint hi = ((x >> j) & 1); // 取x的第j位的值 if (lo ^ hi) { x ^= ((1U << i) | (1U << j)); // 如果第i位和第j位值不同，則交換i和j這兩個位的值，使用異或操作實現 } return x; }/**
反轉整數比特位-仿字符串反轉
*/
uint reverseXOR(uint x)
{
uint n = sizeof(x) * 8;
uint i;
for (i = 0; i < n/2; i++) {
x = swapBits(x, i, n-i-1);
}
return x;
}
復制代碼解2： 采用分治策略，首先交換數字x的相鄰位，然后再是 2 個位交換，然后是 4 個位交換...比如給定一個 8 位數
01101010，則首先交換相鄰位，變成10 01 01 01，然后交換相鄰的 2 個位，得到01 10 01 01，然后再是 4 個位交換，得到0101 0110。總的時間復雜度為O(lgN)，其中 N 為整數的位數。下面給出一個反轉32位整數的代碼，如果整數是64位的可以以此類推。/** * 反轉整數比特位-分治法 */ uint reverseMask(uint x) { assert(sizeof(x) == 4); // special case: only works for 4 bytes (32 bits). x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1); x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2); x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4); x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8); x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16); return x; } 復制代碼系列文章目錄
0. 數據結構和算法面試題系列—C指針、數組和結構體
1. 數據結構和算法面試題系列—字符串
2. 數據結構和算法面試題系列—鏈表
3. 數據結構和算法面試題系列—棧
4. 數據結構和算法面試題系列—二叉堆
5. 數據結構和算法面試題系列—二叉樹基礎
6. 數據結構和算法面試題系列—二叉樹面試題匯總
7. 數據結構和算法面試題系列—二分查找算法詳解
8. 數據結構和算法面試題系列—排序算法之基礎排序
9. 數據結構和算法面試題系列—排序算法之快速排序
10. 數據結構和算法面試題系列—隨機算法總結
11. 數據結構和算法面試題系列—遞歸算法總結
12. 數據結構和算法面試題系列—背包問題總結
13. 數據結構和算法面試題系列—數字題總結其他
此外，在我 簡書的博客 上還整理有《docker相關技術筆記》、《MIT6.828操作系統學習筆記》、《python源碼剖析筆記》等文章，請大家指正。
參考資料
編程珠璣第二版第九章
旋轉數組的二分查找
《算法導論》
歸并排序(遞歸實現+非遞歸實現+自然合并排序) - geeker
《數據結構和算法-C語言實現》
Implement Rand10() Using Rand7() - LeetCode Articles
數學之美番外篇：快排為什么那樣快 – 劉未鵬 | Mind Hacks
網上整理的google面試題
宋勁松老師《Linux C編程》遞歸章節
數據結構與算法-C語言實現
背包問題九講
編程之美
具體數學
微軟、Google等面試題
Reverse Bits – LeetCode原文地址：https://juejin.im/post/5bbc202de51d450e496826e7
總結
以上是生活随笔為你收集整理的那些年，面试中常见的数据结构基础和算法题（下）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 信用卡消费退款，商家让客户付手续费，合理
- 下一篇： 他曾经负债2.5亿，如今身价超过500亿