重學數據結構和演算法（三）之遞歸、二分、字元串匹配
- 2021 年 4 月 23 日
- 筆記
- Android學習筆記
最近學習了極客時間的《數據結構與演算法之美》很有收穫，記錄總結一下。
歡迎學習老師的專欄：數據結構與演算法之美
程式碼地址：//github.com/peiniwan/Arithmetic
遞歸
周末你帶著女朋友去電影院看電影，女朋友問你，咱們現在坐在第幾排啊？電影院裡面太黑了，看不清，沒法數，現在你怎麼辦？別忘了你是程式設計師，這個可難不倒你，遞歸就開始排上用場了。
於是你就問前面一排的人他是第幾排，你想只要在他的數字上加一，就知道自己在哪一排了。但是，前面的人也看不清啊，所以他也問他前面的人。就這樣一排一排往前問，直到問到第一排的人，說我在第一排，然後再這樣一排一排再把數字傳回來。直到你前面的人告訴你他在哪一排，於是你就知道答案了。
我們用遞推公式將它表示出來就是這樣的：
f(n)=f(n-1)+1 其中，f(1)=1
f(n) 表示你想知道自己在哪一排，f(n-1) 表示前面一排所在的排數，f(1)=1 表示第一排的人知道自己在第一排。有了這個遞推公式，我們就可以很輕鬆地將它改為遞歸程式碼，如下：
int f(int n) {
if (n == 1) return 1;
return f(n-1) + 1;
}
遞歸需要滿足的三個條件
- 一個問題的解可以分解為幾個子問題的解
- 這個問題與分解之後的子問題，除了數據規模不同，求解思路完全一樣
- 存在遞歸終止條件
第一排的人不需要再繼續詢問任何人，就知道自己在哪一排，也就是 f(1)=1，這就是遞歸的終止條件。
如何編寫遞歸程式碼？
寫遞歸程式碼最關鍵的是寫出遞推公式，找到終止條件
爬樓梯
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return f(n-1) + f(n-2);
}
寫遞歸程式碼的關鍵就是找到如何將大問題分解為小問題的規律，並且基於此寫出遞推公式，然後再推敲終止條件，最後將遞推公式和終止條件翻譯成程式碼。
人腦幾乎沒辦法把整個「遞」和「歸」的過程一步一步都想清楚。電腦擅長做重複的事情，所以遞歸正和它的胃口。
對於遞歸程式碼，這種試圖想清楚整個遞和歸過程的做法，實際上是進入了一個思維誤區。很多時候，我們理解起來比較吃力，主要原因就是自己給自己製造了這種理解障礙。那正確的思維方式應該是怎樣的呢？
如果一個問題 A 可以分解為若干子問題 B、C、D，你可以假設子問題 B、C、D 已經解決，在此基礎上思考如何解決問題 A。而且，你只需要思考問題 A 與子問題 B、C、D 兩層之間的關係即可，不需要一層一層往下思考子問題與子子問題，子子問題與子子子問題之間的關係。屏蔽掉遞歸細節，這樣子理解起來就簡單多了。
因此，編寫遞歸程式碼的關鍵是，只要遇到遞歸，我們就把它抽象成一個遞推公式，不用想一層層的調用關係，不要試圖用人腦去分解遞歸的每個步驟。
不要陷入思維誤區。
遞歸程式碼要警惕堆棧溢出
函數調用會使用棧來保存臨時變數。每調用一個函數，都會將臨時變數封裝為棧幀壓入記憶體棧，等函數執行完成返回時，才出棧。系統棧或者虛擬機棧空間一般都不大。如果遞歸求解的數據規模很大，調用層次很深，一直壓入棧，就會有堆棧溢出的風險。
那麼，如何避免出現堆棧溢出呢？
// 全局變數，表示遞歸的深度。
int depth = 0;
int f(int n) {
++depth；
if (depth > 1000) throw exception;
if (n == 1) return 1;
return f(n-1) + 1;
}
但這種做法並不能完全解決問題，因為最大允許的遞歸深度跟當前執行緒剩餘的棧空間大小有關，事先無法計算。如果實時計算，程式碼過於複雜，就會影響程式碼的可讀性。所以，如果最大深度比較小，比如 10、50，就可以用這種方法，否則這種方法並不是很實用。
遞歸程式碼要警惕重複計算
為了避免重複計算，我們可以通過一個數據結構（比如散列表）來保存已經求解過的 f(k)。當遞歸調用到 f(k) 時，先看下是否已經求解過了。如果是，則直接從散列表中取值返回，不需要重複計算，這樣就能避免剛講的問題了。
public int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
// hasSolvedList可以理解成一個Map，key是n，value是f(n)
if (hasSolvedList.containsKey(n)) {
return hasSolvedList.get(n);
}
int ret = f(n-1) + f(n-2);
hasSolvedList.put(n, ret);
return ret;
}
電影院遞歸程式碼，空間複雜度並不是 O(1)，而是 O(n)。
怎麼將遞歸程式碼改寫為非遞歸程式碼？
遞歸有利有弊，利是遞歸程式碼的表達力很強，寫起來非常簡潔；而弊就是空間複雜度高、有堆棧溢出的風險、存在重複計算、過多的函數調用會耗時較多等問題
電影院修改
int f(int n) {
int ret = 1;
for (int i = 2; i <= n; ++i) {
ret = ret + 1;
}
return ret;
}
但是這種思路實際上是將遞歸改為了「手動」遞歸，本質並沒有變，而且也並沒有解決前面講到的某些問題，徒增了實現的複雜度。
如何找到「最終推薦人」？
推薦註冊返傭金的這個功能我想你應該不陌生吧？現在很多 App 都有這個功能。這個功能中，用戶 A 推薦用戶 B 來註冊，用戶 B 又推薦了用戶 C 來註冊。我們可以說，用戶 C 的「最終推薦人」為用戶 A，用戶 B 的「最終推薦人」也為用戶 A，而用戶 A 沒有「最終推薦人」。
long findRootReferrerId(long actorId) {
Long referrerId = select referrer_id from [table] where actor_id = actorId;
if (referrerId == null) return actorId;
return findRootReferrerId(referrerId);
}
不過在實際項目中，上面的程式碼並不能工作，為什麼呢？這裡面有兩個問題。
第一，如果遞歸很深，可能會有堆棧溢出的問題。
第二，如果資料庫里存在臟數據，我們還需要處理由此產生的無限遞歸問題。比如 demo 環境下資料庫中，測試工程師為了方便測試，會人為地插入一些數據，就會出現臟數據。如果 A 的推薦人是 B，B 的推薦人是 C，C 的推薦人是 A，這樣就會發生死循環。
第一個問題，我前面已經解答過了，可以用限制遞歸深度來解決。第二個問題，也可以用限制遞歸深度來解決。不過，還有一個更高級的處理方法，就是自動檢測 A-B-C-A 這種「環」的存在。如何來檢測環的存在呢？
調試遞歸
我們平時調試程式碼喜歡使用 IDE 的單步跟蹤功能，像規模比較大、遞歸層次很深的遞歸程式碼，幾乎無法使用這種調試方式。
調試遞歸:
- 列印日誌發現，遞歸值。
- 結合條件斷點進行調試。
public class Recursion {
/**
* 求和
*/
public static int summation(int num) {
if (num == 1) {
return 1;
}
return num + summation(num - 1);
}
/**
* 求二進位
*/
public static int binary(int num) {
StringBuilder sb = new StringBuilder();
if (num > 0) {
summation(num / 2);
int i = num % 2;
sb.append(i);
}
System.out.println(sb.toString());
return -1;
}
/**
* 求n的階乘
*/
public int f(int n) {
if (n == 1) {
return n;
} else {
return n * f(n - 1);
}
}
}
二分查找
有點像分治，底層必須依賴數組，並且還要求數據是有序的。二分查找更適合處理靜態數據，也就是沒有頻繁的數據插入、刪除操作。
這是一個等比數列。其中 n/2k=1 時，k 的值就是總共縮小的次數。而每一次縮小操作只涉及兩個數據的大小比較，所以，經過了 k 次區間縮小操作，時間複雜度就是 O(k)。通過 n/2k=1，我們可以求得 k=log2n，所以時間複雜度就是 O(logn)。
public int binarySearch(int[] arr, int k) {
if (arr.length == 0) {
return -1;
}
if (arr[0] == k) {
return 0;
}
int a = 0;
int b = arr.length - 1;
while (a <= b) {
int m = a + (b - a) / 2;
if (k < arr[m]) {
b = m-1;
} else if (k > arr[m]) {
a = m + 1;
} else {
return m;
}
}
return -1;
}
容易出錯的 3 個地方
- 循環退出條件
注意是 low<=high，而不是 low<high。 - mid 的取值
我們可以將這裡的除以 2 操作轉化成位運算 low+((high-low)>>1)。因為相比除法運算來說，電腦處理位運算要快得多。 - low 和 high 的更新
low=mid+1，high=mid-1。注意這裡的 +1 和 -1，如果直接寫成 low=mid 或者 high=mid，就可能會發生死循環。比如，當 high=3，low=3 時，如果 a[3] 不等於 value，就會導致一直循環不退出。
二分查找除了用循環來實現，還可以用遞歸來實現
// 二分查找的遞歸實現
public int bsearch(int[] a, int n, int val) {
return bsearchInternally(a, 0, n - 1, val);
}
private int bsearchInternally(int[] a, int low, int high, int value) {
if (low > high) return -1;
int mid = low + ((high - low) >> 1);
if (a[mid] == value) {
return mid;
} else if (a[mid] < value) {
return bsearchInternally(a, mid+1, high, value);
} else {
return bsearchInternally(a, low, mid-1, value);
}
}
二分查找應用場景的局限性
首先，二分查找依賴的是順序表結構，簡單點說就是數組。
數組按照下標隨機訪問數據的時間複雜度是 O(1)，而鏈表隨機訪問的時間複雜度是 O(n)。所以，如果數據使用鏈表存儲，二分查找的時間複雜就會變得很高。
其次，二分查找針對的是有序數據。
數據必須是有序的。如果數據沒有序，我們需要先排序
如果我們的數據集合有頻繁的插入和刪除操作，要想用二分查找，要麼每次插入、刪除操作之後保證數據仍然有序，要麼在每次二分查找之前都先進行排序。針對這種動態數據集合，無論哪種方法，維護有序的成本都是很高的。
所以，二分查找只能用在插入、刪除操作不頻繁，一次排序多次查找的場景中。針對動態變化的數據集合，二分查找將不再適用。那針對動態數據集合，如何在其中快速查找某個數據呢？別急，等到二叉樹那一節我會詳細講。
再次，數據量太小不適合二分查找。
如果要處理的數據量很小，完全沒有必要用二分查找，順序遍歷就足夠了。比如我們在一個大小為 10 的數組中查找一個元素，不管用二分查找還是順序遍歷，查找速度都差不多。只有數據量比較大的時候，二分查找的優勢才會比較明顯。
最後，數據量太大也不適合二分查找。
二分查找的底層需要依賴數組這種數據結構，而數組為了支援隨機訪問的特性，要求記憶體空間連續，對記憶體的要求比較苛刻。比如，我們有 1GB 大小的數據，如果希望用數組來存儲，那就需要 1GB 的連續記憶體空間。
如何在 1000 萬個整數中快速查找某個整數？
這個問題並不難。我們的記憶體限制是 100MB，每個數據大小是 8 位元組，最簡單的辦法就是將數據存儲在數組中，記憶體佔用差不多是 80MB，符合記憶體的限制。藉助今天講的內容，我們可以先對這 1000 萬數據從小到大排序，然後再利用二分查找演算法，就可以快速地查找想要的數據了。
雖然大部分情況下，用二分查找可以解決的問題，用散列表、二叉樹都可以解決。但是，我們後面會講，不管是散列表還是二叉樹，都會需要比較多的額外的記憶體空間。如果用散列表或者二叉樹來存儲這 1000 萬的數據，用 100MB 的記憶體肯定是存不下的。而二分查找底層依賴的是數組，除了數據本身之外，不需要額外存儲其他資訊，是最省記憶體空間的存儲方式，所以剛好能在限定的記憶體大小下解決這個問題。
二分查找變形
十個二分九個錯
上一節講的只是二分查找中最簡單的一種情況，在不存在重複元素的有序數組中，查找值等於給定值的元素。最簡單的二分查找寫起來確實不難，但是，二分查找的變形問題就沒那麼好寫了。
變體一：查找第一個值等於給定值的元素
如下面這樣一個有序數組，其中，a[5]，a[6]，a[7] 的值都等於 8，是重複的數據。我們希望查找第一個等於 8 的數據，也就是下標是 5 的元素。
如果我們用上一節課講的二分查找的程式碼實現，首先拿 8 與區間的中間值 a[4] 比較，8 比 6 大，於是在下標 5 到 9 之間繼續查找。下標 5 和 9 的中間位置是下標 7，a[7] 正好等於 8，所以程式碼就返回了。
儘管 a[7] 也等於 8，但它並不是我們想要找的第一個等於 8 的元素，因為第一個值等於 8 的元素是數組下標為 5 的元素。
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
if ((mid == 0) || (a[mid - 1] != value)) return mid;
else high = mid - 1;
}
}
return -1;
}
變體二：查找最後一個值等於給定值的元素
前面的問題是查找第一個值等於給定值的元素，我現在把問題稍微改一下，查找最後一個值等於給定值的元素，又該如何做呢？
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
else low = mid + 1;
}
}
return -1;
}
變體三：查找第一個大於等於給定值的元素
在有序數組中，查找第一個大於等於給定值的元素。比如，數組中存儲的這樣一個序列：3，4，6，7，10。如果查找第一個大於等於 5 的元素，那就是 6。
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] >= value) {
if ((mid == 0) || (a[mid - 1] < value)) return mid;
else high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
變體四：查找最後一個小於等於給定值的元素
我們來看最後一種二分查找的變形問題，查找最後一個小於等於給定值的元素。比如，數組中存儲了這樣一組數據：3，5，6，8，9，10。最後一個小於等於 7 的元素就是 6。
public int bsearch7(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else {
if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
else low = mid + 1;
}
}
return -1;
}
字元串匹配
我們用的最多的就是程式語言提供的字元串查找函數，比如 Java 中的 indexOf()，Python 中的 find() 函數等，它們底層就是依賴接下來要講的字元串匹配演算法。
BF 演算法和 RK 演算法、BM 演算法和 KMP 演算法。
BF 演算法
BF 演算法中的 BF 是 Brute Force 的縮寫，中文叫作暴力匹配演算法，也叫樸素匹配演算法。
我們在字元串 A 中查找字元串 B，那字元串 A 就是主串，字元串 B 就是模式串。我們把主串的長度記作 n，模式串的長度記作 m。因為我們是在主串中查找模式串，所以 n>m。
BF 演算法的思想可以用一句話來概括，那就是，我們在主串中，檢查起始位置分別是 0、1、2…n-m 且長度為 m 的 n-m+1 個子串，看有沒有跟模式串匹配的（看圖）。
我們每次都比對 m 個字元，要比對 n-m+1 次，所以，這種演算法的最壞情況時間複雜度是 O(n* m)。
/**
* BF演算法
* 檢查起始位置分別是 0、1、2…n-m 且長度為 m 的 n-m+1 個子串，看有沒有跟模式串匹配的
*/
public static int bfFind(String S, String T, int pos) {
char[] arr1 = S.toCharArray();
char[] arr2 = T.toCharArray();
int i = pos;
int j = 0;
while (i < arr1.length && j < arr2.length) {
if (arr1[i] == arr2[j]) {
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}
if (j == arr2.length) return i - j;
else return -1;
}
儘管理論上，BF 演算法的時間複雜度很高，是 O(n* m)，但在實際的開發中，它卻是一個比較常用的字元串匹配演算法。
第一，實際的軟體開發中，大部分情況下，模式串和主串的長度都不會太長。
第二，樸素字元串匹配演算法思想簡單，程式碼實現也非常簡單。
RK 演算法
BF 演算法的升級版。
BF每次檢查主串與子串是否匹配，需要依次比對每個字元，所以 BF 演算法的時間複雜度就比較高，是 O(n* m)。我們對樸素的字元串匹配演算法稍加改造，引入哈希演算法，時間複雜度立刻就會降低。
RK 演算法的思路是這樣的：我們通過哈希演算法對主串中的 n-m+1 個子串分別求哈希值，然後逐個與模式串的哈希值比較大小。如果某個子串的哈希值與模式串相等，那就說明對應的子串和模式串匹配了（這裡先不考慮哈希衝突的問題，後面我們會講到）。因為哈希值是一個數字，數字之間比較是否相等是非常快速的，所以模式串和子串比較的效率就提高了。
比如要處理的字元串只包含 a～z 這 26 個小寫字母，那我們就用二十六進位來表示一個字元串。我們把 a～z 這 26 個字元映射到 0～25 這 26 個數字，a 就表示 0，b 就表示 1，以此類推，z 表示 25。
在十進位的表示法中，一個數字的值是通過下面的方式計算出來的。對應到二十六進位，一個包含 a 到 z 這 26 個字元的字元串，計算哈希的時候，我們只需要把進位從 10 改成 26 就可以。
這種哈希演算法有一個特點，在主串中，相鄰兩個子串的哈希值的計算公式有一定關係。我這有個個例子，你先找一下規律，再來看我後面的講解。
從這裡例子中，我們很容易就能得出這樣的規律：相鄰兩個子串 s[i-1] 和 s[i]（i 表示子串在主串中的起始位置，子串的長度都為 m），對應的哈希值計算公式有交集，也就是說，我們可以使用 s[i-1] 的哈希值很快的計算出 s[i] 的哈希值。如果用公式表示的話，就是下面這個樣子：
