前言

??我大學的時候比較瘋狂，除了上課的時候，基本都是在機房刷題，當然，有時候連上課都在想題目，紙上寫好代碼，一下課就沖進機房把代碼敲了，目的很單純，為了沖排行榜，就像玩游戲一樣，享受霸榜的快感，
??當年主要是在 「 杭電OJ 」 和 「 北大OJ 」 這兩個在線平臺上刷題，那時候還沒有（「 LeetCode 」、「 牛客 」、「 洛谷 」 這些先如今非常🔥的刷題網站），后來參加作業以后，剩余的時間不多了，也就沒怎么刷了， 但是 「 演算法思維 」 也就是靠上大學那「 四年 」鍛煉出來的，


??當年題目少，刷題的人也少，所以勉強還沖到過第一，現在去看已經 58 名了，可見 「 長江后浪推前浪 」，前浪 S 在沙灘上，時勢造英雄啊！


??北大人才輩出，相對題目也比較難，所以明顯有點 「 心有余而力不足 」 的感覺，刷的相對就少很多，而且這個 OJ 也沒什么人維護了，看我的簽名，當時竟然還想著給博客引點流，現在估計都沒什么人去那個網站了吧，

本文已收錄于專欄 💜《夜深人靜寫演算法》💜
??這篇文章的主要目的是為尚未接觸演算法的朋友提供一個學習演算法的路線指引，但是實際學習程序還是需要看個人的毅力和堅持，那么，讓我們先來看下需要按照什么樣的順序來進行刷題吧，下圖代表的是 LeetCode 經典的演算法和資料結構的總綱，

點擊我跳轉末尾 獲取 粉絲專屬 《演算法和資料結構》原始碼，

---

一、資料結構

LeetCode演算法分類 🌌《演算法入門指引》🌌

1、線性表

1）順序表

a、順序存盤
??順序存盤結構，是指用一段地址連續的存盤單元依次存盤線性表的資料元素，

b、存盤方式
??在編程語言中，用一維陣列來實作順序存盤結構，在C語言中，把第一個資料元素存盤到下標為 0 的位置中，把第 2 個資料元素存盤到下標為 1 的位置中，以此類推，

c、長度和容量
??陣列的長度指的是陣列當前有多少個元素，陣列的容量指的是陣列最大能夠存放多少個元素，如果陣列元素大于最大能存盤的范圍，在程式上是不允許的，可能會產生意想不到的問題，實作上是需要規避的，

??如上圖所示，陣列的長度為 5，即紅色部分；容量為 8，即紅色 加 藍色部分，

d、資料結構定義

#define MAXN 1024
#define DataType int        // (1)

struct SeqList {
    DataType data[MAXN];    // (2)
    int length;             // (3)
}; 

• ( 1 ) (1) (1) 陣列型別為DataType，定義為int；
• ( 2 ) (2) (2) SeqList定義的就是一個最多存放MAXN個元素的陣列，MAXN代表陣列容量；
• ( 3 ) (3) (3) length代表陣列長度，即當前的元素個數，

??有關順序表的更多內容，可以參考：《畫解資料結構》（1 - 1）- 陣列，

---

2）鏈表

??鏈表分為 單向鏈表 和 雙向鏈表，這里以單向鏈表為例，
??對于順序存盤的結構，如陣列，最大的缺點就是：插入 和 洗掉 的時候需要移動大量的元素，所以，基于前人的智慧，他們發明了鏈表，

a、鏈表定義
??鏈表 是由一個個 結點 組成，每個 結點 之間通過 鏈接關系 串聯起來，每個 結點 都有一個 后繼節點，最后一個 結點 的 后繼結點 為 空結點，如下圖所示：

??由鏈接關系A -> B組織起來的兩個結點，B被稱為A的后繼結點，A被稱為B的前驅結點，
??鏈表 分為 單向鏈表、雙向鏈表、回圈鏈表 等等，本文要介紹的鏈表是 單向鏈表，
??由于鏈表是由一個個 結點 組成，所以我們先來看下 結點 的實作，

b、結點結構體定義

typedef int DataType;
struct ListNode {
    DataType data;  // (1)
    ListNode *next; // (2)
};

• ( 1 ) (1) (1) 資料域：可以是任意型別，由編碼的人自行指定；這段代碼中，利用typedef將它和int同名，本文的 資料域 也會全部采用int型別進行講解；
• ( 2 ) (2) (2) 指標域：指向 后繼結點 的地址；
• 一個結點包含的兩部分如下圖所示：
  

c、結點的創建
??我們通過 C語言 中的庫函式malloc來創建一個 鏈表結點，然后對 資料域 和 指標域 進行賦值，代碼實作如下：

ListNode *ListCreateNode(DataType data) {
    ListNode *node = (ListNode *) malloc ( sizeof(ListNode) ); // (1)
    node->data = data;                                         // (2)
    node->next = NULL;                                         // (3)
    return node;                                               // (4)
}

• ( 1 ) (1) (1) 利用系統庫函式malloc分配一塊記憶體空間，用來存放ListNode即鏈表結點物件；
• ( 2 ) (2) (2) 將 資料域 置為函式傳參data；
• ( 3 ) (3) (3) 將 指標域 置空，代表這是一個孤立的 鏈表結點；
• ( 4 ) (4) (4) 回傳這個結點的指標，
• 創建完畢以后，這個孤立結點如下所示：
  

??有關順序表的更多內容，可以參考：《畫解資料結構》（1 - 3）- 鏈表，

---

3）堆疊

a、堆疊的定義

??堆疊 是僅限在 表尾 進行 插入 和 洗掉 的 線性表，
??堆疊 又被稱為 后進先出 （Last In First Out） 的線性表，簡稱 LIFO ，

b、堆疊頂
??堆疊 是一個線性表，我們把允許 插入 和 洗掉 的一端稱為 堆疊頂，

3、堆疊底
??和 堆疊頂 相對，另一端稱為 堆疊底，實際上，堆疊底的元素我們不需要關心，

??有關堆疊的更多內容，可以參考：《畫解資料結構》（1 - 5）- 堆疊，

---

4）佇列

1、佇列的定義
??佇列 是僅限在 一端 進行 插入，另一端 進行 洗掉 的 線性表，
??佇列 又被稱為 先進先出 （First In First Out） 的線性表，簡稱 FIFO ，

2、隊首
??允許進行元素洗掉的一端稱為 隊首，如下圖所示：

3、隊尾
??允許進行元素插入的一端稱為 隊尾，如下圖所示：

??有關佇列的更多內容，可以參考：《畫解資料結構》（1 - 6）- 佇列，

---

5）樹狀陣列

a、樹狀陣列的含義
??名曰樹狀陣列，那么究竟它是樹還是陣列呢？陣列在物理空間上是連續的，而樹是通過父子關系關聯起來的，而樹狀陣列正是這兩種關系的結合，首先在存盤空間上它是以陣列的形式存盤的，即下標連續；其次，對于兩個陣列下標 x ， y ( x < y ) x，y(x < y) x，y(x<y)，如果滿足： x + 2 k = y ( k 等 于 x 的 二 進 制 表 示 中 末 尾 0 的 個 數 ) x + 2^k = y (k 等于 x 的二進制表示中末尾 0 的個數) x+2k=y(k等于x的二進制表示中末尾0的個數)，那么定義 ( y , x ) (y, x) (y,x) 為一組樹上的父子關系，其中 y y y 為父結點， x x x 為子結點，

??如上圖所示，其中 A 為普通陣列，C 為樹狀陣列（C 在物理空間上和 A 一樣都是連續存盤的），樹狀陣列的第 4 個元素 C 4 C_4 C4? 的父結點為 C 8 C_8 C8? (4的二進制表示為 ( 100 ) 2 (100)_2 (100)2?，所以 k = 2 k=2 k=2，那么 4 + 2 2 = 8 4 + 2^2 = 8 4+22=8)， C 6 C_6 C6? 和 C 7 C_7 C7? 同理， C 2 C_2 C2? 和 C 3 C_3 C3? 的父結點為 C 4 C_4 C4?，同樣也是可以用上面的關系得出的，那么從定義出發，奇數下標一定是葉子結點，

b、結點的含義
??然后我們來看樹狀陣列上的結點 C i C_i Ci? 具體表示什么，這時候就需要利用樹的遞回性質了，
??我們定義 C i C_i Ci? 的值為它的所有子結點的值 和 A i A_i Ai? 的總和，之前提到當 i i i 為奇數時 C i C_i Ci? 一定為葉子結點，所以有 C i = A i C_i = A_i Ci?=Ai? ( i i i 為奇數 )，從圖三-1-1中可以得出如下等式組：
{ C 1 = A 1 C 2 = C 1 + A 2 = A 1 + A 2 C 3 = A 3 C 4 = C 2 + C 3 + A 4 = A 1 + A 2 + A 3 + A 4 C 5 = A 5 C 6 = C 5 + A 6 = A 5 + A 6 C 7 = A 7 C 8 = C 4 + C 6 + C 7 + A 8 = A 1 + A 2 + A 3 + A 4 + A 5 + A 6 + A 7 + A 8 \begin {cases} C_1 = A_1 \\ C_2 = C_1 + A_2 = A_1 + A_2 \\ C_3 = A_3 \\ C_4 = C_2 + C_3 + A_4 = A_1 + A_2 + A_3 + A_4 \\ C_5 = A_5 \\ C_6 = C_5 + A_6 = A_5 + A_6 \\ C_7 = A_7 \\ C_8 = C_4 + C_6 + C_7 + A_8 = A_1 + A_2 + A_3 + A_4 + A_5 + A_6 + A_7 + A_8 \end{cases} ??????????????????????????????C1?=A1?C2?=C1?+A2?=A1?+A2?C3?=A3?C4?=C2?+C3?+A4?=A1?+A2?+A3?+A4?C5?=A5?C6?=C5?+A6?=A5?+A6?C7?=A7?C8?=C4?+C6?+C7?+A8?=A1?+A2?+A3?+A4?+A5?+A6?+A7?+A8??
??我們從上面的公式中可以發現，其實 C i C_i Ci? 還有一種更加普適的定義，它表示的其實是一段原陣列 A A A 的區間和，根據定義，右區間的下標是很明顯的，一定是 i i i，即 C i C_i Ci? 表示的區間的最后一個元素一定是 A i A_i Ai?，那么接下來就是要求 C i C_i Ci? 表示的左區間的下標是什么，從圖中可以看出，其實就是順著 C i C_i Ci? 的最左兒子一直找直到找到葉子結點，那個葉子結點就是 C i C_i Ci? 表示區間的第一個元素，
??更加具體的，如果 i i i 的二進制表示為 ( ? ? ? ? 1000 ) 2 (????1000)_2 (????1000)2?，那么它最左邊的兒子就是 ( ? ? ? ? 0100 ) 2 (????0100)_2 (????0100)2?，這一步是通過結點父子關系的定義進行逆推得到，并且這條路徑可以表示如下： ( ? ? ? ? 1000 ) 2 → ( ? ? ? ? 0100 ) 2 → ( ? ? ? ? 0010 ) 2 → ( ? ? ? ? 0001 ) 2 (????1000)_2 \to (????0100)_2 \to (????0010)_2 \to (????0001)_2 (????1000)2?→(????0100)2?→(????0010)2?→(????0001)2???這時候， ( ? ? ? ? 0001 ) 2 (????0001)_2 (????0001)2? 已經是葉子結點了，所以它就是 C i C_i Ci? 能夠表示的第一個元素的下標，那么我們發現，如果用 k k k 來表示 i i i 的二進制末尾 0 的個數， C i C_i Ci? 能夠表示的 A A A 陣列的區間的元素個數為 2 k 2^k 2k，又因為該區間的最后一個數一定是 A i A_i Ai?，所以有如下公式： C i = ∑ j = i ? 2 k + 1 i A j C_i = \sum_{ j = i - 2^k + 1}^i A_j Ci?=j=i?2k+1∑i?Aj?
??比較直觀的理解就是，左區間的下標是通過 右區間下標 減去 2 k 2^k 2k 加上 1 得出，

c、求和操作
??明白了 C i C_i Ci? 的含義后，我們需要通過它來求 ∑ j = 1 i A j \sum_{j=1}^{i} A_j ∑j=1i?Aj?，也就是之前提到的 s u m ( i ) sum(i) sum(i) 函式，為了簡化問題，用一個函式 l o w b i t ( i ) lowbit(i) lowbit(i) 來表示 2 k 2^k 2k ( k k k 等于 i i i 的二進制表示中末尾 0 的個數)，那么：
s u m ( i ) = A 1 + A 2 + . . . + A i = A 1 + A 2 + A i ? 2 k + A i ? 2 k + 1 + . . . + A i = A 1 + A 2 + A i ? 2 k + C i = s u m ( i ? 2 k ) + C i = s u m ( i ? l o w b i t ( i ) ) + C i \begin{aligned}sum(i) &= A_1 + A_2 + ... + A_i \\ &= A_1 + A_2 + A_{i-2^k} + A_{i-2^k+1} + ... + A_i\\ &= A_1 + A_2 + A_{i-2^k} + C_i\\ &= sum(i - 2^k) + C_i\\ &= sum( i - lowbit(i) ) + C_i \end{aligned} sum(i)?=A1?+A2?+...+Ai?=A1?+A2?+Ai?2k?+Ai?2k+1?+...+Ai?=A1?+A2?+Ai?2k?+Ci?=sum(i?2k)+Ci?=sum(i?lowbit(i))+Ci????由于 C i C_i Ci? 已知，所以 s u m ( i ) sum(i) sum(i) 可以通過遞回求解，遞回出口為當 i = 0 i = 0 i=0 時，回傳 0， s u m ( i ) sum(i) sum(i) 函式的函式主體只需要一行代碼：

int sum(int i) {
    return i ? C[i] + sum(i - lowbit(i)):0;
}

??觀察 i - lowbit(i)，其實就是將 i i i 的二進制表示的最后一個 1 去掉，最多只有 l o g i log_i logi? 個 1，所以求 s u m ( i ) sum(i) sum(i) 的最壞時間復雜度為 O ( l o g i ) O(log_i) O(logi?)，由于遞回的時候常數開銷比較大，所以一般寫成迭代的形式更好，寫成迭代形式的代碼如下：

int sum(int i) {
    int s = 0;
    while (i >= 1) {
        s += c[i];
        i -= lowbit(i);
    }
    return s;
}

d、更新操作
??更新操作就是之前提到的 a d d ( i , 1 ) add(i, 1) add(i,1) 和 a d d ( i , ? 1 ) add(i, -1) add(i,?1)，更加具體得，可以推廣到 a d d ( i , v ) add(i, v) add(i,v)，表示的其實就是 A i = A i + v A_i = A_i + v Ai?=Ai?+v，但是我們不能在原陣列 A A A 上操作，而是要像求和操作一樣，在樹狀陣列 C C C 上進行操作，
??從求和公式可以知道 A i A_i Ai? 的改變只會影響 C i C_i Ci? 及其祖先結點，即 A 5 A_5 A5? 的改變影響的是 C 5 、 C 6 、 C 8 C_5、C_6、C_8 C5?、C6?、C8?；而 A 1 A_1 A1? 的改變影響的是 C 1 、 C 2 、 C 4 、 C 8 C_1、C_2、C_4、C_8 C1?、C2?、C4?、C8?，
??我們知道，樹狀陣列上的父子關系 ( y , x ) (y, x) (y,x) 滿足 x + 2 k = y x + 2^k = y x+2k=y，所以我們可以通過這個公式從葉子結點不斷往上遞回，直到 y y y 超過最大值 m a x n maxn maxn 為止，祖先結點最多為 l o g m a x n log_{maxn} logmaxn? 個， a d d ( i , v ) add(i, v) add(i,v) 的主體代碼（去除邊界判斷）也只有一行代碼：

const int maxn = 100000;

void add(int i, int v){
    if(i <= maxn){
        C[i] += v, add( i + lowbit(i), v);
    }
 }

??和求和操作類似，遞回的時候常數開銷比較大，所以一般寫成迭代的形式更好，寫成迭代形式的代碼如下：

const int maxn = 100000;

void add(int i, int v) {
    while (i <= maxn) {
        c[i] += v;
        i += lowbit(i);
    }
}

e、lowbit 函式 O(1) 實作
??上文提到的兩個函式 s u m ( i ) sum(i) sum(i) 和 a d d ( i , v ) add(i, v) add(i,v) 都用到了一個函式叫 l o w b i t ( i ) lowbit(i) lowbit(i)，表示的是 2 k 2^k 2k，其中 k k k 為 i i i 的二進制表示末尾 0 的個數，那么最簡單的實作辦法就是通過位運算的右移，回圈判斷最后一位是 0 還是 1，從而統計末尾 0 的個數，一旦發現 1 后統計完畢，計數器保存的值就是 k k k，當然這樣的做法總的復雜度為 O ( l o g i ) O( log_i ) O(logi?)，一個32位的整數最多可能進行31次運算，
??這里介紹一種 O ( 1 ) O(1) O(1) 的方法計算 2 k 2^k 2k 的方法，

f、補碼
??來看一段補碼小知識：清楚補碼的表示的可以跳過這一段，計算機中的符號數有三種表示方法，即原碼、反碼和補碼，三種表示方法均有符號位和數值位兩部分，符號位都是用0表示“正”，用1表示“負”，而數值位，三種表示方法各不相同，這里只討論整數補碼的情況，在計算機系統中，數值一律用補碼來表示和存盤，原因在于，使用補碼，可以將符號位和數值域統一處理；同時，加法和減法也可以統一處理，整數補碼的表示分兩種：
??正數：正數的補碼即其二進制表示；例如一個 8 位二進制的整數 +5，它的補碼就是 ( 00000101 ) 2 (00000101)_2 (00000101)2?；
??負數：負數的補碼即將其整數對應的二進制表示所有位取反(包括符號位)后加 1；
例如一個 8 位二進制的整數 -5，它的二進制表示是 ( 00000101 ) 2 (00000101)_2 (00000101)2?，取反后為 ( 11111010 ) 2 (11111010)_2 (11111010)2?，再加 1 就是 ( 11111011 ) 2 (11111011)_2 (11111011)2?，這就是它的補碼了，
??下面的等式可以幫助理解補碼在計算機中是如何作業的： + 5 + ( ? 5 ) = 00000101 + 11111011 = 1 00000000 ( 溢 出 了 ! ! ! ) = 0 +5 + (-5) = 00000101 + 11111011 = 1 \ 00000000 (溢位了!!!) = 0 +5+(?5)=00000101+11111011=1 00000000(溢出了!!!)=0
??這里的加法沒有將數值位和符號位分開，而是統一作為二進制位進行計算，由于表示的是8進制的整數，所以多出的那個最高位的1會直接舍去，使得結果變成了0，而實際的十進制計算結果也是0，正確，

x & (-x)
??補碼復習完畢，那么來看下下面這個運算式的含義：

	x & (-x);

??首先進行 & 運算，我們需要將 x x x 和 ? x -x ?x 都轉化成補碼，然后再看 & 之后會發生什么，
??令 x x x 的二進制表示為 ( X 0 X 1 X 2 … X n ? 2 X n ? 1 ) 2 (X_0X_1X_2…X_{n-2}X_{n-1})_2 (X0?X1?X2?…Xn?2?Xn?1?)2? 這里的 X 0 X_0 X0? 表示符號位，我們假設 x x x 的二進制表示的末尾是連續的 k k k 個 0，則有 ( X i = 0 ∣ n ? k ≤ i < n ) (X_i = 0 | n-k \le i < n) (Xi?=0∣n?k≤i<n)
?? x x x 的補碼就是由三部分組成（其中 X n ? k ? 1 = 1 X_{n-k-1} = 1 Xn?k?1?=1）： ( 符 號 位 0 ) ( X 1 X 2 … X n ? k ? 1 ) ( 00...00 ? k ) 2 (符號位0)(X_1X_2…X_{n-k-1})(\underbrace {00...00}_{\rm k})_2 (符號位0)(X1?X2?…Xn?k?1?)(k 00...00??)2?
?? ? x -x ?x 的補碼也是由三部分組成（其中 Y n ? k ? 1 = 1 Y_{n-k-1} = 1 Yn?k?1?=1）： ( 符 號 位 1 ) ( Y 1 Y 2 … Y n ? k ? 1 ) ( 00...00 ? k ) 2 (符號位1)(Y_1Y_2…Y_{n-k-1})(\underbrace {00...00}_{\rm k})_2 (符號位1)(Y1?Y2?…Yn?k?1?)(k 00...00??)2?
??根據補碼的定義，可得 X i + Y i = 1 ( i ∈ [ 0 , n ? k ? 1 ) ) X_i + Y_i = 1 ( i \in [0, n-k-1) ) Xi?+Yi?=1(i∈[0,n?k?1))；
??那么 x & (-x)也就顯而易見了，為 ( 1 00...00 ? k ) 2 (1\underbrace {00...00}_{\rm k})_2 (1k 00...00??)2?，表示成十進制為 2 k 2^k 2k，正好是我們要求的 l o w b i t ( x ) lowbit(x) lowbit(x) ，由于&的優先級低于-，所以代碼可以這樣寫：

int lowbit(int x) {
    return x & -x;
}

??至此，樹狀陣列的基礎內容就到此結束了，三個函式就詮釋了樹狀陣列的所有內容，并且都只需要一行代碼實作，單次操作的時間復雜度為 O ( l o g n ) O( log_n ) O(logn?)，空間復雜度為 O ( n ) O(n) O(n)，所以它是一種性價比非常高的輕量級資料結構，
??有關樹狀陣列的更多內容，可以參考：夜深人靜寫演算法（十三）- 樹狀陣列，

---

2、樹

1）二叉樹

??樹是一種重要的非線性資料結構，直觀的看，它是資料元素按分支關系組織起來的結構，二叉樹是每個結點最多有兩個子樹的有序樹，子樹的根被稱作 “左子樹” 和 “右子樹”，
??二叉樹支持增刪改查，BST、AVL、線段樹、堆 都是二叉樹，下面將針對不同的二叉樹進行分類講解，

2）二叉搜索樹

??二叉搜索樹（BST）又稱二叉查找樹或二叉排序樹，一棵二叉搜索樹是以二叉樹來組織的，可以使用一個鏈表資料結構來表示，其中每一個結點就是一個物件，當然也可以使用順序表來表示，第 i i i 個元素存盤父結點， 2 i 2i 2i 存盤它的左子樹， 2 i + 1 2i+1 2i+1存盤它的右子樹，
??除了鍵和位置資料之外，每個結點還包含屬性 left、right和parent，分別指向結點的左孩子、右孩子和父結點，如果某個孩子結點或父結點不存在，則相應屬性的值為空，
??有關二叉搜索樹的內容，將會在《畫解資料結構》（2 - 1）- 二叉搜索樹 文章中進行連載，

3）堆

??堆總是一棵完全二叉樹，我們將根結點最大的堆叫做最大堆或大根堆，根結點最小的堆叫做最小堆或小根堆，常見的堆有二叉堆、斐波那契堆等，
??堆是非線性資料結構，相當于一維陣列，有兩個直接后繼，
??有關堆的內容，將會在《畫解資料結構》（2 - 3）- 堆 與 優先佇列 文章中進行連載，

4）AVL樹

??AVL樹我沒寫過，但是我發4，有生之年，我一定得寫一個！先在這篇文章立個 flag！

5）線段樹

??有關線段樹的相關內容，可以參考以下文章：夜深人靜寫演算法（四十一）- 線段樹，

6）字典樹

??有關字典樹的相關內容，可以參考以下文章：夜深人靜寫演算法（七）- 字典樹，

7）哈夫曼樹

??有關哈夫曼樹的相關內容，可以參考以下文章：夜深人靜寫演算法（十五）- 霍夫曼樹，

8）紅黑樹

??紅黑樹一般在面試中會問一些基礎結構，實際刷題程序中都可以用 哈希表、平衡樹AVL 來替代，所以我這里就不過多做介紹了，

9）并查集

??有關并查集的相關內容，可以參考以下文章：夜深人靜寫演算法（五）- 并查集，

3、圖

1）最短路

??有關并查集的相關內容，可以參考以下文章：夜深人靜寫演算法（二十三）- 最短路，

2）強連通分量

??有關并查集的相關內容，可以參考以下文章：夜深人靜寫演算法（四十二）- 有向圖強連通和2-sat問題，

4、哈希表

??有關并查集的相關內容，可以參考以下文章：《畫解資料結構》（1 - 8）- 哈希表，

二、演算法

1、排序

1）冒泡排序

?

圖示	含義
■ 的柱形	代表尚未排好序的數
■ 的柱形	代表正在執行比較的兩個數
■ 的柱形	代表已經排好序的數

??我們看到，首先需要將 「第一個元素」 和 「第二個元素」 進行 「比較」，如果 前者 大于 后者，則進行 「交換」，然后再比較 「第二個元素」 和 「第三個元素」 ，以此類推，直到 「最大的那個元素」 被移動到 「最后的位置」 ，
??然后，進行第二輪「比較」，直到 「次大的那個元素」 被移動到 「倒數第二的位置」 ，
??最后，經過一定輪次的「比較」 和 「交換」之后，一定可以保證所有元素都是 「升序」 排列的，

---

2）選擇排序

?

圖示	含義
■ 的柱形	代表尚未排好序的數
■ 的柱形	代表正在執行 比較 的數
■ 的柱形	代表已經排好序的數
■ 的柱形	有兩種：1、記錄最小元素 2、執行交換的元素

??我們發現，首先從 「第一個元素」 到 「最后一個元素」 中選擇出一個 「最小的元素」，和 「第一個元素」 進行 「交換」；
??然后，從 「第二個元素」 到 「最后一個元素」 中選擇出一個 「最小的元素」，和 「第二個元素」 進行 「交換」，
??最后，一定可以保證所有元素都是 「升序」 排列的，

---

3）插入排序

?

圖示	含義
■ 的柱形	代表尚未排好序的數
■ 的柱形	代表正在執行 比較 和 移動 的數
■ 的柱形	代表已經排好序的數
■ 的柱形	代表待執行插入的數

??我們看到，首先需要將 「第二個元素」 和 「第一個元素」 進行 「比較」，如果 前者 小于等于 后者，則將 后者 進行向后 「移動」，前者 則執行插入；
??然后，進行第二輪「比較」，即 「第三個元素」 和 「第二個元素」、「第一個元素」 進行 「比較」， 直到 「前三個元素」 保持有序 ，
??最后，經過一定輪次的「比較」 和 「移動」之后，一定可以保證所有元素都是 「升序」 排列的，

---

4）希爾排序

?

??一下子看完不是很理解，沒有關系，我們把這幾個程序分拆開來，第一趟分解后，如圖所示：


??增量為 4，所有元素總共分為 4 組，分別為 [8, 3]、[5, 7]、[6, 10]、[4, 2]，同組內部分別執行插入排序，得到 [3, 8]、[5, 7]、[6, 10]、[2, 4]（由于每組只有兩個元素，所以升序的情況位置不變，降序的情況執行組內元素位置交換，抖動一下代表保持原順序不變，有一種 “我不換 ~~ 我不換” 的意思在里面 ），

??第二趟分解后，如圖所示：


??增量為 2，所有元素總共分為 2 組，分別為 [3, 6, 8, 10]、[5, 2, 7, 4]，同組內部分別執行插入排序，[3, 6, 8, 10]已經升序，保持原樣；[5, 2, 7, 4] 執行三次插入排序后變成 [2, 4, 5, 7]，
??第三趟分解后，如圖所示：


??增量為 1，所有元素歸為 1 組，為 [3, 2, 6, 4, 8, 5, 10, 7]，對它執行簡單插入排序，執行完畢后，必然可以保證所有元素有序，

---

5）歸并排序

?

圖示	含義
■ 的柱形	代表尚未排好序的數
■ 的柱形	代表已經排好序的數
其他顏色 ■ 的柱形	正在遞回、歸并中的數

??我們發現，首先將 「 8個元素 」 分成 「 4個元素 」，再將 「 4個元素 」 分成 「 2個元素 」，然后 「比較」這「 2個元素 」的值，使其在自己的原地陣列內有序，然后兩個 「 2個元素 」 的陣列歸并變成 「 4個元素 」 的 「升序」陣列，再將兩個「 4個元素 」 的陣列歸并變成 「 8個元素 」 的 「升序」陣列，

---

6）快速排序

?

圖示	含義
■ 的柱形	代表尚未排好序的數
■ 的柱形	代表隨機選定的基準數
■ 的柱形	代表已經排序好的數
■ 的柱形	代表正在遍歷比較的數
■ 的柱形	代表比基準數小的數
■ 的柱形	代表比基準數大的數

??我們發現，首先隨機選擇了一個 7 作為「 基準數 」，并且將它和最左邊的數交換，然后往后依次遍歷判斷，小于 7 的數為 「 綠色 」 ，大于 7 的數為「 紫色 」，遍歷完畢以后，將 7 和 「 下標最大的那個比 7 小的數 」交換位置，至此，7的左邊位置上的數都小于它，右邊位置上的數都大于它，左邊和右邊的數繼續遞回求解即可，

---

7）計數排序

?

圖示	含義
■ 的柱形	計數為 0 的數
■ 的柱形	計數為 1 的數
■ 的柱形	計數為 2 的數
■ 的柱形	計數為 3 的數
■ 的柱形	計數為 4 的數

??我們看到，首先程式生成了一個區間范圍為 [ 1 , 9 ] [1, 9] [1,9] 的 「 計數器陣列 」，并且一開始所有值的計數都為 0，
??然后，遍歷列舉「 原陣列 」的所有元素，在 元素值 對應的計數器上執行 「 計數 」 操作，
??最后，遍歷列舉「 計數器陣列 」，按照陣列中元素個數放回到 「 原陣列 」 中，這樣，一定可以保證所有元素都是 「升序」 排列的，

---

8）基數排序

?

「 紅色的數字位 」 代表需要進行 「 哈希 」 映射到給定 「 佇列 」 中的數字位，
??我們看到，首先程式生成了一個區間范圍為 [ 0 , 9 ] [0, 9] [0,9] 的 「 基數佇列 」，
??然后，總共進行了 4 輪「 迭代 」（因為最大的數總共 4 個數位），
??每次迭代，遍歷列舉 「 原陣列 」 中的所有數，并且取得本次迭代對應位的數字，通過「 哈希 」，映射到它「 對應的佇列 」中 ，然后將 「 佇列 」 中的資料按順序塞回 「 原陣列 」 完成一次「 迭代 」，4 次「 迭代 」后，一定可以保證所有元素都是 「升序」 排列的，

2、列舉

1）線性列舉

??線性列舉，一般配合的 資料結構 是 【陣列】 或者 【鏈表】，實作方式就是一個回圈，正因為只有一個回圈，所以線性列舉解決的問題一般比較簡單，而且很容易從題目中看出來，

??撰寫一個函式，將輸入的字串反轉過來，輸入字串以字符陣列 char[] 的形式給出，
必須原地修改輸入陣列、使用 O(1) 的額外空間解決這一問題，
??樣例輸入： [ “ a ” , “ b ” , “ c ” , “ d ” ] [“a”, “b”, “c”, “d”] [“a”,“b”,“c”,“d”]
??樣例輸出： [ “ d ” , “ c ” , “ b ” , “ a ” ] [ “d”, “c”, “b”, “a”] [“d”,“c”,“b”,“a”]
??原題出處： LeetCode 344. 反轉字串

??翻轉的含義，相當于就是 第一個字符 和 最后一個交換，第二個字符 和 最后第二個交換，… 以此類推，所以我們首先實作一個交換變數的函式 swap，然后再列舉 第一個字符、第二個字符、第三個字符 …… 即可，
??對于第 i i i 個字符，它的交換物件是 第 l e n ? i ? 1 len-i-1 len?i?1 個字符 (其中 l e n len len 為字串長度)，swap函式的實作，可以參考：《C語言入門100例》 - 例2 | 交換變數，
??線性列舉的程序為 O ( n ) O(n) O(n)，交換變數為 O ( 1 ) O(1) O(1)，兩個程序是相乘的關系，所以整個演算法的時間復雜度為 O ( n ) O(n) O(n)，

class Solution {
public:
    void swap(char& a, char& b) {            // (1)
        char tmp = a;
        a = b;
        b = tmp;
    }
    void reverseString(vector<char>& s) {
        int len = s.size();
        for(int i = 0; i < len / 2; ++i) {   // (2)
            swap(s[i], s[len-i-1]);
        }
    }
};

• ( 1 ) (1) (1) 實作一個變數交換的函式，其中&是C++中的參考，在函式傳參是經常用到，被稱為：參考傳遞(pass-by-reference)，即被調函式的形式引數雖然也作為區域變數在堆疊中開辟了記憶體空間
  ，但是這時存放的是由主調函式放進來的實參變數的地址，被調函式對形參的任何操作都被處理成間接尋址，即通過堆疊中存放的地址訪問主調函式中的實參變數，

簡而言之，函式呼叫的引數，可以傳參考，從而使得函式回傳時，傳參值的改變依舊生效，

• ( 2 ) (2) (2) 這一步是做的線性列舉，注意列舉范圍是 [ 0 , l e n / 2 ? 1 ] [0, len/2-1] [0,len/2?1]，

2）二分列舉

??能用二分列舉的問題，一定可以用線性列舉來實作，只是時間上的差別，二分列舉的時間復雜度一般為對數級，效率上會高不少，同時，實作難度也會略微有所上升，我們通過平時開發時遇到的常見問題來舉個例子，

??軟體開發的時候，會有版本的概念，由于每個版本都是基于之前的版本開發的，所以錯誤的版本之后的所有版本都是錯的，假設你有 n n n 個版本 [ 1 , 2 , . . . , n ] [1, 2, ..., n] [1,2,...,n]，你想找出導致之后所有版本出錯的第一個錯誤的版本，可以通過呼叫bool isBadVersion(version)介面來判斷版本號version是否在單元測驗中出錯，實作一個函式來查找第一個錯誤的版本，應該盡量減少對呼叫 API 的次數，
??樣例輸入： 5 5 5 和 b a d = 4 bad = 4 bad=4
??樣例輸出： 4 4 4
??原題出處： LeetCode 278. 第一個錯誤的版本

??由題意可得，我們呼叫它提供的 API 時，回傳值分布如下： 000...000111...111 000...000111...111 000...000111...111其中 0 代表false，1 代表true；也就是一旦出現 1，就再也不會出現 0 了，所以基于這思路，我們可以二分位置；

歸納總結為 2 種情況，如下：
??1）當前二分到的位置 m i d mid mid，給出的版本是錯誤，那么從當前位置以后的版本不需要再檢測了（因為一定也是錯誤的），并且我們可以肯定，出錯的位置一定在 [ l , m i d ] [l, mid] [l,mid]；并且 m i d mid mid 是一個可行解，記錄下來；
??2）當前二分到的位置 m i d mid mid，給出的版本是正確，則出錯位置可能在 [ m i d + 1 , r ] [mid+1, r] [mid+1,r]；
??由于每次都是將區間折半，所以時間復雜度為 O ( l o g 2 n ) O(log_2n) O(log2?n)，

class Solution {
public:
    int firstBadVersion(int n) {
        long long l = 1, r = n;             // (1)
        long long ans = (long long)n + 1;
        while(l <= r) {
            long long mid = (l + r) / 2;
            if( isBadVersion(mid) ) {       
                ans = mid;                  // (2)
                r = mid - 1;
            }else {
                l = mid + 1;                // (3)
            }
        }
        return ans;
    }
};

• ( 1 ) (1) (1) 需要這里，這里兩個區間相加可能超過 int，所以需要采用 64 位整型long long；
• ( 2 ) (2) (2) 找到錯誤版本的嫌疑區間 [ l , m i d ] [l, mid] [l,mid]，并且 m i d mid mid 是確定的候選嫌疑位置；
• ( 3 ) (3) (3) 錯誤版本不可能落在 [ l , m i d ] [l, mid] [l,mid]，所以可能在 [ m i d + 1 , r ] [mid+1, r] [mid+1,r]，需要繼續二分迭代；

3）三分列舉

4）前綴和

5）雙指標

??給定一個長度為 n ( 1 ≤ n ≤ 1 0 7 ) n (1 \le n \le 10^7) n(1≤n≤107) 的字串 s s s，求一個最長的滿足所有字符不重復的子串的長度，
??樣例輸入：" a b c a b c b b g abcabcbbg abcabcbbg"
??樣例輸出： 3 3 3
??原題出處： LeetCode 3. 無重復字符的最長子串

??我們考慮一個子串以 s i s_i si? 為左端點， s j s_j sj? 為右端點，且 s [ i : j ? 1 ] s[i:j-1] s[i:j?1] 中不存在重復字符， s [ i : j ] s[i:j] s[i:j] 中存在重復字符（換言之， s j s_j sj? 和 s [ i : j ? 1 ] s[i:j-1] s[i:j?1] 中某個字符相同），如圖所示：

??那么我們沒必要再去檢測 s [ i : j + 1 ] s[i:j+1] s[i:j+1]， s [ i : j + 2 ] s[i:j+2] s[i:j+2]， s [ i : n ? 1 ] s[i:n-1] s[i:n?1] 這幾個字串的合法性，因為當前情況 s [ i : j ] s[i:j] s[i:j] 是非法的，而這些字串是完全包含 s [ i : j ] s[i:j] s[i:j] 的，所以它們必然也是不合法的，
??那么我們可以把列舉的左端點自增，即： i = i + 1 i = i +1 i=i+1，這時，按照樸素演算法的實作，右端點需要重置，即 j = i j = i j=i，實際上這里的右端點可以不動，
??可以這么考慮，由于 s j s_j sj? 這個字符和 s [ i : j ? 1 ] s[i:j-1] s[i:j?1] 中的字符產生了重復，假設這個重復的字符的下標為 k k k，那么 i i i 必須滿足 i > k i \gt k i>k，換言之， i i i 可以一直自增，直到 i = k + 1 i = k+1 i=k+1，如圖所示：

??這個問題是 雙指標 問題的原題，詳細的演算法可以參考：夜深人靜寫演算法（二十八）- 尺取法，
??兩個指標都只會遞增各一次，所以時間復雜度為 O ( n ) O(n) O(n)，

class Solution {
    int hash[257];

public:
    int lengthOfLongestSubstring(string s) {
        memset(hash, 0, sizeof(hash));
        int maxLen = 0;
        int i = 0, j = -1;             // (1)
        int len = s.length();          // (2)
        while(j++ < len - 1) {
            ++hash[ s[j] ];            // (3)
            while(hash[ s[j] ] > 1) {  // (4)
                --hash[ s[i] ];        // (5)
                ++i;
            }
            if(j - i + 1 > maxLen) {   // (6)
                maxLen = j - i + 1;
            }
        }
        return maxLen;
    }
};

• ( 1 ) (1) (1) 代表一開始是空串；
• ( 2 ) (2) (2) 之所以要這么做，是因為s.length()是無符號整型，當 j == -1的情況為無符號整型的最大值，永遠都無法進入下面的while(j++ < len - 1)這個回圈；
• ( 3 ) (3) (3) 嘗試向右移動 右指標；
• ( 4 ) (4) (4) 合法性判定：所有字符個數不超過1；
• ( 5 ) (5) (5) 嘗試向右移動 左指標；
• ( 6 ) (6) (6) 更新最大合法長度；

3、動態規劃

1）遞推問題

??遞推問題作為動態規劃的基礎，是最好掌握的，也是必須掌握的，它有點類似于高中數學中的數列，通過 前幾項的值 推匯出 當前項的值，

??你正在爬樓梯，需要 n n n 階你才能到達樓頂，每次你可以爬 1 1 1 或 2 2 2 個臺階，你有多少種不同的方法可以爬到樓頂呢？

??假設我們已經到了第 n n n 階樓梯，那么它可以是從 n ? 1 n-1 n?1 階過來的，也可以是從 n ? 2 n-2 n?2 階過來的（但是，不可能是從 n ? 3 n-3 n?3 階直接過來的），所以如果達到第 n n n 階的方案數為 f [ n ] f[n] f[n]，那么到達 n ? 1 n-1 n?1 階就是 f [ n ? 1 ] f[n-1] f[n?1]，到達 n ? 2 n-2 n?2 階 就是 f [ n ? 2 ] f[n-2] f[n?2]，所以可以得出： f [ n ] = f [ n ? 1 ] + f [ n ? 2 ] f[n] = f[n-1] + f[n-2] f[n]=f[n?1]+f[n?2]??其中，當 n = 0 n=0 n=0 時方案數為 1，代表初始情況； n = 1 n=1 n=1 時方案數為 1，代表走了一步，遞推計算即可，
??以上就是最簡單的動態規劃問題，也是一個經典的數列：斐波那契數列 的求解方式，它通過一個遞推公式，將原本指數級的問題轉化成了線性的，時間復雜度為 O ( n ) O(n) O(n)，
??C語言代碼實作如下：

int f[1000];
int climbStairs(int n){
    f[0] = f[1] = 1;
    for(int i = 2; i <= n; ++i) {
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

2）線性DP

1、最小花費

??陣列的每個下標作為一個階梯，第 i i i 個階梯對應著一個非負數的體力花費值 c o s t [ i ] cost[i] cost[i]（下標從 0 開始），每當爬上一個階梯，都要花費對應的體力值，一旦支付了相應的體力值，就可以選擇 向上爬一個階梯 或者 爬兩個階梯，求找出達到樓層頂部的最低花費，在開始時，可以選擇從下標為 0 0 0 或 1 1 1 的元素作為初始階梯，

??令走到第 i i i 層的最小消耗為 f [ i ] f[i] f[i]，假設當前的位置在 i i i 層樓梯，那么只可能從 i ? 1 i-1 i?1 層過來，或者 i ? 2 i-2 i?2 層過來；
????如果從 i ? 1 i-1 i?1 層過來，則需要消耗體力值： f [ i ? 1 ] + c o s t [ i ? 1 ] f[i-1] + cost[i-1] f[i?1]+cost[i?1]；
????如果從 i ? 2 i-2 i?2 層過來，則需要消耗體力值： f [ i ? 2 ] + c o s t [ i ? 2 ] f[i-2] + cost[i-2] f[i?2]+cost[i?2]；
??起點可以在第 0 或者 第 1 層，于是有狀態轉移方程： f [ i ] = { 0 i = 0 , 1 min ? ( f [ i ? 1 ] + c o s t [ i ? 1 ] , f [ i ? 2 ] + c o s t [ i ? 2 ] ) i > 1 f[i] = \begin{cases} 0 & i=0,1\\ \min ( f[i-1] + cost[i-1], f[i-2] + cost[i-2] ) & i > 1\end{cases} f[i]={0min(f[i?1]+cost[i?1],f[i?2]+cost[i?2])?i=0,1i>1?

??這個問題和一開始的遞推問題的區別在于：一個是求前兩項的和，一個是求最小值，這里就涉及到了動態取舍的問題，也就是動態規劃的思想，
??如果從前往后思考，每次都有兩種選擇，時間復雜度為 O ( 2 n ) O(2^n) O(2n)，轉化成動態規劃以后，只需要一個回圈，時間復雜度為 O ( n ) O(n) O(n)，
??C語言代碼實作如下：

int f[1024];
int min(int a, int b) {
    return a < b ? a : b;
}
int minCostClimbingStairs(int* cost, int costSize){
    f[0] = 0;
    f[1] = 0;
    for(int i = 2; i <= costSize; ++i) {
        f[i] = min(f[i-1] + cost[i-1], f[i-2] + cost[i-2]);
    }
    return f[costSize];
}

2、最大子段和

??給定一個整數陣列 n u m s nums nums ，找到一個具有最大和的連續子陣列（子陣列最少包含一個元素），回傳其最大和，

??由于要求的是連續的子陣列，所以對于第 i i i 個元素，狀態轉移一定是從 i ? 1 i-1 i?1 個元素轉移過來的，基于這一點，可以令 f [ i ] f[i] f[i] 表示以 i i i 號元素結尾的最大值，
??那么很自然，這個最大值必然包含 n u m s [ i ] nums[i] nums[i] 這個元素，那么要不要包含 n u m s [ i ? 1 ] , n u m s [ i ? 2 ] , n u m s [ i ? 3 ] , . . . , n u m s [ k ] nums[i-1],nums[i-2],nums[i-3],...,nums[k] nums[i?1],nums[i?2],nums[i?3],...,nums[k] 呢？其實就是看第 i ? 1 i-1 i?1 號元素結尾的最大值是否大于零，也就是：當 f [ i ? 1 ] ≤ 0 f[i-1] \le 0 f[i?1]≤0 時，則 前 i ? 1 i-1 i?1 個元素是沒必要包含進來的，所以就有狀態轉移方程： f [ i ] = { n u m s [ 0 ] i = 0 n u m s [ i ] f [ i ? 1 ] ≤ 0 n u m s [ i ] + f [ i ? 1 ] f [ i ? 1 ] > 0 f[i] = \begin{cases} nums[0] & i = 0 \\ nums[i] & f[i-1] \le 0 \\ nums[i] + f[i-1] & f[i-1] > 0\end{cases} f[i]=??????nums[0]nums[i]nums[i]+f[i?1]?i=0f[i?1]≤0f[i?1]>0?一層回圈列舉后，取 m a x ( f [ i ] ) max(f[i]) max(f[i]) 就是答案了，只需要一個回圈，時間復雜度為 O ( n ) O(n) O(n)，
??C語言代碼實作如下：

int dp[30010];
int max(int a, int b) {
    return a > b ? a : b;
}

int maxSubArray(int* nums, int numsSize){
    int maxValue = nums[0];
    dp[0] = nums[0];
    for(int i = 1; i < numsSize; ++i) {
        dp[i] = nums[i];
        if(dp[i-1] > 0) {
            dp[i] += dp[i-1];
        }
        maxValue = max(maxValue, dp[i]);
    }
    return maxValue;
}

3、最長單調子序列

??給定一個長度為 n ( 1 ≤ n ≤ 1000 ) n(1 \le n \le 1000) n(1≤n≤1000) 的陣列 a i a_i ai?，求給出它的最長遞增子序列的長度，

??在看這個問題之前，我們先來明確一些概念：單調序列、單調子序列、最大長單調子序列，
??單調序列 就是一個滿足某種單調性的陣列序列，比如 單調遞增序列、單調遞減序列、單調不增序列、單調不減序列，舉幾個簡單的例子：
??單調遞增序列：1，2，3，7，9
??單調遞減序列：9，8，4，2，1
??單調不增序列：9，8，8，5，2
??單調不減序列：1，2，2，5，5
??一個比較直觀的單調遞增序列的例子就是一個樓梯的側面，

??我們可以把這個樓梯每一階的高度用一個數字表示，得到一個單調遞增序列，如圖所示：

??單調子序列 指的是任意一個陣列序列，按順序選擇一些元素組成一個新的序列，并且滿足單調性，對于一個長度為 n n n 的序列，每個元素可以選擇 “取” 或者 “不取”，所以最多情況下，有 2 n 2^n 2n 個單調子序列，
??如圖所示，代表的是序列：[1，2，4，6，3，5，9]

??其中 [1，2，6] 為它的一個長度為 3 的單調子序列，如圖所示；

??[1，3，6] 則不是，因為 3 和 6 的順序不是原序列中的順序；[1，4，3] 也不是，因為它不滿足單調性，
??最長單調子序列 是指對于原陣列序列，能夠找到的元素個數最多的單調子序列，
??還是以 [1，2，4，6，3，5，9] 為例，它的最長單調子序列為：[1，2，4，6，9]，長度為 5；

??當然，也可以是 [1，2，3，5，9]，長度同樣為 5， ??那么，接下來，我們看下如何通過動態規劃的方法來求解 最長遞增子序列，
??對于陣列序列 a i ( 1 ≤ i ≤ n ) a_i(1 \le i \le n) ai?(1≤i≤n)，令 f [ i ] f[i] f[i] 表示以第 i i i 個數 a i a_i ai? 結尾的最長遞增子序列的長度，那么，我們考慮以第 i i i 個數 a i a_i ai? 結尾的最長遞增子序列，它在這個序列中的前一個數一定是 a j ( 1 ≤ j < i ) a_j(1 \le j < i) aj?(1≤j<i) 中的一個，所以，如果我們已經知道了 f [ j ] f[j] f[j]，那么就有 f [ i ] = f [ j ] + 1 f[i] = f[j] + 1 f[i]=f[j]+1，顯然，我們還需要滿足 a j < a i a_j < a_i aj?<ai? 這個遞增的限制條件，
??那么就可以得出狀態轉移方程： f [ i ] = max ? j = 1 i ? 1 ( f [ j ] ∣ a j < a i ) + 1 f[i] = \max_{j=1}^{i-1} (f[j] \ | \ a_j < a_i) + 1 f[i]=j=1maxi?1?(f[j] ∣ aj?<ai?)+1??這里 f [ j ] f[j] f[j] 是 f [ i ] f[i] f[i] 的子結構，而 m a x ( f [ j ] ) max(f[j]) max(f[j]) 是 f [ i ] f[i] f[i] 的最優子結構，當然我們需要考慮一種情況，就是沒有找到最優子結構的時候，例如： i = 1 i=1 i=1 或者 不存在 a j < a i a_j < a_i aj?<ai? 的 j j j，此時 f [ i ] = 1 f[i] = 1 f[i]=1，表示 a i a_i ai? 本身是一個長度為 1 1 1 的最長遞增子序列，
?? f [ i ] f[i] f[i] 陣列可以通過兩層回圈來求解，如下圖表所示：

??狀態數 f [ . . . ] f[...] f[...] 總共 O ( n ) O(n) O(n) 個，狀態轉移的消耗為 O ( n ) O(n) O(n)，所以總的時間復雜度為 O ( n 2 ) O(n^2) O(n2)，所以對于這類問題，一般能夠接受的 n n n 的范圍在千級別，也就是 1000 , 2000 , 3000... 1000, 2000, 3000 ... 1000,2000,3000...，如果是 n = 10000 , 100000 n=10000, 100000 n=10000,100000 的情況，就需要考慮優化了，
??有關最長單調子序列的問題，還有 O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n) 的優化演算法，具體方法可以參考以下文章：夜深人靜寫演算法（二十）- 最長單調子序列，

3）二維DP

1、最長公共子序列

??給定兩個陣列序列 a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1?,a2?,...,an? 和 b 1 , b 2 , . . . , b m b_1, b_2, ..., b_m b1?,b2?,...,bm?，其中 n , m ≤ 1000 n,m \le 1000 n,m≤1000，求兩個陣列的最長公共子序列，

??考慮兩個陣列序列 a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1?,a2?,...,an? 和 b 1 , b 2 , . . . , b m b_1, b_2, ..., b_m b1?,b2?,...,bm?，對于 a a a 序列中第 i i i 個元素 a i a_i ai? 和 b b b 序列中的第 j j j 個元素 b j b_j bj?，有兩種情況：
?? ( 1 ) (1) (1) 相等即 a i = = b j a_i == b_j ai?==bj? 的情況，這個時候如果前綴序列 a 1 , a 2 , . . . , a i ? 1 a_1, a_2, ..., a_{i-1} a1?,a2?,...,ai?1? 和 b 1 , b 2 , . . . , b j ? 1 b_1, b_2, ..., b_{j-1} b1?,b2?,...,bj?1? 的最長公共子序列已經求出來了，記為 x x x 的話，那么很顯然，在兩個序列分別加入 a i a_i ai? 和 b j b_j bj? 以后，長度又貢獻了 1，所以 a 1 , a 2 , . . . , a i a_1, a_2, ..., a_{i} a1?,a2?,...,ai? 和 b 1 , b 2 , . . . , b j b_1, b_2, ..., b_{j} b1?,b2?,...,bj? 的最長公共子序列就是 x + 1 x+1 x+1；

?? ( 2 ) (2) (2) 不相等即 a i ≠ b j a_i \neq b_j ai??=bj? 的情況，這個時候我們可以把問題拆分成兩個更小的子問題，即 分別去掉 a i a_i ai? 和 b j b_j bj? 的情況，如圖所示：

??去掉 a i a_i ai? 以后，問題轉變為求： a 1 , a 2 , . . . , a i ? 1 a_1, a_2, ..., a_{i-1} a1?,a2?,...,ai?1? 和 b 1 , b 2 , . . . , b j b_1, b_2, ..., b_{j} b1?,b2?,...,bj? 的最長公共子序列；
??去掉 b j b_j bj? 以后，問題轉變為求： a 1 , a 2 , . . . , a i a_1, a_2, ..., a_{i} a1?,a2?,...,ai? 和 b 1 , b 2 , . . . , b j ? 1 b_1, b_2, ..., b_{j-1} b1?,b2?,...,bj?1? 的最長公共子序列；
??根據上面的兩種情況的討論，我們發現，在任何時候，我們都在求 a a a 的前綴 和 b b b 的前綴的最長公共序列，所以可以這么定義狀態：用 f [ i ] [ j ] f[i][j] f[i][j] 表示 a 1 , a 2 , . . . , a i a_1, a_2, ..., a_{i} a1?,a2?,...,ai? 和 b 1 , b 2 , . . . , b j b_1, b_2, ..., b_{j} b1?,b2?,...,bj? 的最長公共子序列，
??在設計狀態的程序中，我們已經無形中把狀態轉移也設計好了，狀態轉移方程如下： f [ i ] [ j ] = { 0 i = 0 o r j = 0 f [ i ? 1 ] [ j ? 1 ] + 1 i , j > 0 , a i = b j max ? ( f [ i ] [ j ? 1 ] , f [ i ? 1 ] [ j ] ) i , j > 0 , a i ≠ b j f[i][j] = \begin{cases}0 & i=0\ or\ j=0 \\ f[i-1][j-1] + 1 & i,j>0,a_i=b_j \\ \max(f[i][j-1], f[i-1][j]) & i,j>0,a_i \neq b_j\end{cases} f[i][j]=??????0f[i?1][j?1]+1max(f[i][j?1],f[i?1][j])?i=0 or j=0i,j>0,ai?=bj?i,j>0,ai??=bj????對于 i = 0 i=0 i=0 或者 j = 0 j=0 j=0 代表的是：其中一個序列的長度為 0，那么最長公共子序列的長度肯定就是 0 了；
??其余兩種情況，就是我們上文提到的 a i a_i ai? 和 b j b_j bj? “相等” 與 “不相等” 的兩種情況下的狀態轉移，如圖所示，代表了字串 “GATCGTGAGC” 和 “AGTACG” 求解最長公共子序列的 f [ i ] [ j ] ( i , j > 0 ) f[i][j] (i,j > 0) f[i][j](i,j>0) 的矩陣，

??對于長度分別為 n n n 和 m m m 的兩個序列，求解它們的最長公共子序列時，狀態數總共有 O ( n m ) O(nm) O(nm) 個，每次狀態轉移的消耗為 O ( 1 ) O(1) O(1)，所以總的時間復雜度為 O ( n m ) O(nm) O(nm)，
??對于 f [ i ] [ j ] f[i][j] f[i][j] 這個狀態，求解程序中，只依賴于 f [ i ] [ j ? 1 ] f[i][j-1] f[i][j?1]、 f [ i ? 1 ] [ j ? 1 ] f[i-1][j-1] f[i?1][j?1]、 f [ i ? 1 ] [ j ] f[i-1][j] f[i?1][j]，

??即每次求解只需要有 上一行 和 這一行 的狀態即可，所以可以采用滾動陣列進行優化，將狀態轉移方程變成： f [ c u r ] [ j ] = { f [ l a s t ] [ j ? 1 ] + 1 j > 0 , a i = b j max ? ( f [ c u r ] [ j ? 1 ] , f [ l a s t ] [ j ] ) j > 0 , a i ≠ b j f[cur][j] = \begin{cases}f[last][j-1] + 1 & j>0,a_i=b_j \\ \max(f[cur][j-1], f[last][j]) & j>0,a_i \neq b_j\end{cases} f[cur][j]={f[last][j?1]+1max(f[cur][j?1],f[last][j])?j>0,ai?=bj?j>0,ai??=bj????只需要簡單將 i i i 替換成 c u r cur cur， i ? 1 i-1 i?1 替換成 l a s t last last 即可，這樣就把原本 O ( n m ) O(nm) O(nm) 的空間復雜度變成了 O ( p ) O(p) O(p)，其中 p = min ? ( n , m ) p = \min(n,m) p=min(n,m)，

• 優化后的 C++ 代碼實作如下：

typedef char ValueType;
const int maxn = 5010;
int f[2][maxn];

int getLCSLength(int hsize, ValueType *h, int vsize, ValueType *v) {
    memset(f, 0, sizeof(f));
    int cur = 1, last = 0;
    for (int i = 1; i <= vsize; ++i) {
        for (int j = 1; j <= hsize; ++j) {
            if (v[i] == h[j])
                f[cur][j] = f[last][j - 1] + 1;
            else
                f[cur][j] = max(f[cur][j - 1], f[last][j]);
        }
        swap(last, cur);
    }
    return f[last][hsize];
}

??有關于 最長公共子序列 的更多內容，可以參考以下內容：夜深人靜寫演算法（二十一）- 最長公共子序列，

2、最小編輯距離

??長度為 n n n 的源字串 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1?,a2?,...,an?，經過一些給定操作變成長度為 m m m 的目標字串 b 1 , b 2 , . . . b m b_1,b_2,...b_m b1?,b2?,...bm?，操作包括如下三種：
??1） I n s e r t Insert Insert：在源字串中插入一個字符，插入消耗為 I I I；
??2） D e l e t e Delete Delete：在源字串中洗掉一個字符，洗掉消耗為 D D D；
??3） R e p l a c e Replace Replace：將源字串中的一個字符替換成另一個字符，替換消耗為 R R R；
求最少的總消耗，其中 n , m ≤ 1000 n,m \le 1000 n,m≤1000，

??令 f [ i ] [ j ] f[i][j] f[i][j] 表示源字串 a 1 , a 2 , . . . , a i a_1,a_2,...,a_i a1?,a2?,...,ai? 經過上述三種操作變成目標字串 b 1 , b 2 , . . . b j b_1,b_2,...b_j b1?,b2?,...bj? 的最少消耗，
??假設 a 1 , a 2 , . . . , a i a_1,a_2,...,a_{i} a1?,a2?,...,ai? 變成 b 1 , b 2 , . . . b j ? 1 b_1,b_2,...b_{j-1} b1?,b2?,...bj?1? 的最少消耗已經求出，等于 f [ i ] [ j ? 1 ] f[i][j-1] f[i][j?1]，則需要在 a [ i ] a[i] a[i] 的后面插入一個字符 b j b_j bj?，那么產生的消耗為： f [ i ] [ j ? 1 ] + I f[i][j-1] + I f[i][j?1]+I 如圖所示，源字串為 “AGTA”，目標字串為 “GATCGT” 的情況下，將源字串變成 "“GATCG” 的最小消耗為 f [ i ] [ j ? 1 ] f[i][j-1] f[i][j?1]，那么只要在源字串最后再插入一個 ‘T’，就可以把源字串變成目標字串 “GATCGT”；

??假設 a 1 , a 2 , . . . , a i ? 1 a_1,a_2,...,a_{i-1} a1?,a2?,...,ai?1? 變成 b 1 , b 2 , . . . b j b_1,b_2,...b_{j} b1?,b2?,...bj? 的最少消耗已經求出，等于 f [ i ? 1 ] [ j ] f[i-1][j] f[i?1][j]，則需要把 a i a_i ai? 個刪掉，那么產生的消耗為： f [ i ? 1 ] [ j ] + D f[i-1][j] + D f[i?1][j]+D 如圖所示，源字串為 “AGTA”，目標字串為 “GATCGT” 的情況下，將 “AGT” 變成目標字串的最小消耗為 f [ i ? 1 ] [ j ] f[i-1][j] f[i?1][j]，那么只要把源字串最后一個’A’刪掉，就可以把源字串變成目標字串；

??假設 a 1 , a 2 , . . . , a i ? 1 a_1,a_2,...,a_{i-1} a1?,a2?,...,ai?1? 變成 b 1 , b 2 , . . . b j ? 1 b_1,b_2,...b_{j-1} b1?,b2?,...bj?1? 的最少消耗已經求出，等于 f [ i ? 1 ] [ j ? 1 ] f[i-1][j-1] f[i?1][j?1]，則將 a i a_i ai? 替換成 b j b_j bj?， a 1 , a 2 , . . . , a i a_1,a_2,...,a_{i} a1?,a2?,...,ai? 就可以變成 b 1 , b 2 , . . . b j b_1,b_2,...b_{j} b1?,b2?,...bj?，替換時需要考慮 a i = b j a_i=b_j ai?=bj? 和 a i ≠ b j a_i \neq b_j ai??=bj? 的情況，所以替換產生的消耗為： f [ i ? 1 ] [ j ? 1 ] + { 0 a i = b j R a i ≠ b j f[i-1][j-1] + \begin{cases} 0 & a_i=b_j \\ R & a_i \neq b_j\end{cases} f[i?1][j?1]+{0R?ai?=bj?ai??=bj?? 如圖所示，源字串為 “AGTA”，目標字串為 “GATCGT” 的情況下，將 “AGT” 變成 “GATCGT” 的最小消耗為 f [ i ? 1 ] [ j ? 1 ] f[i-1][j-1] f[i?1][j?1]，那么只要將 源字串 的最后一個字符 替換為 目標字串 的最后一個字符 ，就可以把源字串變成目標字串；替換時根據 源字串 和 目標字串 原本是否相等來決定消耗；

• 邊界情況主要考慮以下幾種：
  ??a. 空串變成目標串 即 f [ 0 ] [ j ] f[0][j] f[0][j]，總共需要插入 j j j 個字符，所以 f [ 0 ] [ j ] = f [ 0 ] [ j ? 1 ] + I f[0][j] = f[0][j-1] + I f[0][j]=f[0][j?1]+I；
  ??b. 源字串變成空串 即 f [ i ] [ 0 ] f[i][0] f[i][0]，總共需要洗掉 i i i 個字符，所以 f [ i ] [ 0 ] = f [ i ? 1 ] [ 0 ] + D f[i][0] = f[i-1][0] + D f[i][0]=f[i?1][0]+D；
  ??c. 空串變成空串 即 f [ 0 ] [ 0 ] = 0 f[0][0] = 0 f[0][0]=0

??將上述所有狀態進行一個整合，得到狀態轉移方程如下： f [ i ] [ j ] = { 0 i = 0 , j = 0 f [ i ] [ j ? 1 ] + I i = 0 , j > 0 f [ i ? 1 ] [ j ] + D i > 0 , j = 0 min ? i > 0 , j > 0 { f [ i ] [ j ? 1 ] + I f [ i ? 1 ] [ j ] + D f [ i ? 1 ] [ j ? 1 ] + R a i ≠ b j f[i][j] = \begin{cases}0 & i=0,j=0\\f[i][j-1]+I & i=0,j>0\\ f[i-1][j] + D & i>0,j=0 \\ \min_{i>0,j>0} \begin{cases} f[i][j-1] + I\\ f[i-1][j] + D\\ f[i-1][j-1] + R_{a_i \neq b_j}\end{cases}\end{cases} f[i][j]=????????????????????0f[i][j?1]+If[i?1][j]+Dmini>0,j>0???????f[i][j?1]+If[i?1][j]+Df[i?1][j?1]+Rai??=bj????i=0,j=0i=0,j>0i>0,j=0
??通過這個狀態矩陣，最后計算得到 f [ n ] [ m ] f[n][m] f[n][m] 就是該題所求 "源字串 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1?,a2?,...,an?，經過 插入、洗掉、替換 變成目標字串 b 1 , b 2 , . . . b m b_1,b_2,...b_m b1?,b2?,...bm?" 的最少消耗了，特殊的，當 I = D = R = 1 I = D = R = 1 I=D=R=1 時， f [ n ] [ m ] f[n][m] f[n][m] 就是字串 a a a 和 b b b 的萊文斯坦距離，
??狀態總數 O ( n m ) O(nm) O(nm)，每次狀態轉移的消耗為 O ( 1 ) O(1) O(1)，所以總的時間復雜度為 O ( n m ) O(nm) O(nm)，空間上可以采用滾動陣列進行優化，具體優化方案可以參考 最長公共子序列 的求解程序，
??如圖所示的是一張源字串 “AGTACG” 到目標字串 “GATCGTGAGC” 的萊文斯坦距離圖，

??有關最小編輯距離的詳細內容，可以參考：夜深人靜寫演算法（二十二）- 最小編輯距離，

3、雙串匹配問題

??給定一個 匹配字串 s (只包含小寫字母) 和一個 模式字串 p (包含小寫字母和兩種額外字符：'.'和 '*')，要求實作一個支持 '.'和 '*'的正則運算式匹配（'*'前面保證有字符），
??'.'匹配任意單個字符
??'*'匹配零個或多個前面的那一個元素

??這是個經典的 串匹配 問題，可以按照 最長公共子序列 的思路去解決，令 f ( i , j ) f(i, j) f(i,j) 代表的是 匹配串前綴 s[0:i] 和 模式串前綴 p[0:j] 是否有匹配，只有兩個值： 0 代表 不匹配， 1 代表 匹配，
??于是，對模式串進行分情況討論：
??1）當 p[j] 為.時，代表 s[i] 為任意字符時，它都能夠匹配（沒毛病吧？沒毛病），所以問題就轉化成了求 匹配串前綴 s[0:i-1] 和 模式串前綴 p[0:j-1] 是否有匹配的問題，也就是這種情況下 f ( i , j ) = f ( i ? 1 , j ? 1 ) f(i, j) = f(i-1, j-1) f(i,j)=f(i?1,j?1)，如圖1所示：


??2）當 p[j] 為*時，由于*前面保證有字符，所以拿到字符 p[j-1]，分情況討論：
????2.a）如果 p[j-1] 為.時，可以匹配所有 s[0:i] 的后綴，這種情況下，只要 f ( k , j ? 2 ) f(k, j-2) f(k,j?2) 為 1， f ( i , j ) f(i, j) f(i,j) 就為 1；其中 k ∈ [ 0 , i ] k \in [0, i] k∈[0,i]，如下圖所示：


????2.b）如果 p[j-1] 非.時，只有當 s[0:i] 的后綴 字符全為 p[j-1] 時，才能去匹配 s[0:i] 的前綴，同樣轉化成 f ( k , j ? 2 ) f(k, j-2) f(k,j?2) 的子問題，如下圖所示：


??3）當 p[j] 為其他任意字符時，一旦 p[j] 和 s[i] 不匹配，就認為 f ( i , j ) = 0 f(i, j) = 0 f(i,j)=0，否則 f ( i , j ) = f ( i ? 1 , j ? 1 ) f(i, j) = f(i-1, j-1) f(i,j)=f(i?1,j?1)，如下圖所示：


??最后，這個問題可以采用 記憶化搜索 求解，并且需要考慮一些邊界條件，邊界條件可以參考代碼實作中的講解，記憶化搜索會在下文仔細講解，
??匹配串的長度為 n n n，模式串的長度為 m m m，狀態數： O ( n m ) O(nm) O(nm)，狀態轉移： O ( n ) O(n) O(n)，時間復雜度： O ( n 2 m ) O(n^2m) O(n2m)，

4）記憶化搜索

??給定一個 n ( n ≤ 45 ) n(n \le 45) n(n≤45)，求 斐波那契數列的第 n n n 項的值，要求用遞回實作，

??那么，我們只需要套用上面的遞回函式，并且處理好遞回出口，就能把它寫成遞回的形式，C語言 代碼實作如下：

int f(unsigned int n) {
    if(n <= 1) {
        return 1;
    }
    return f(n-1) + f(n-2);
}

??遞回求解的程序如下：

??這是一棵二叉樹，樹的高度為 n n n，所以粗看遞回訪問時結點數為 2 n 2^n 2n，但是仔細看，對于任何一棵子樹而言，左子樹的高度一定比右子樹的高度大，所以不是一棵嚴格的完全二叉樹，為了探究它實際的時間復雜度，我們改下代碼：

int f(unsigned int n) {
    ++c[n];
    if(n <= 1) {
        return 1;
    }
    return f(n-1) + f(n-2);
}

??加了一句代碼 ++c[n];，引入一個計數器，來看下在不同的 n n n 的情況下， f ( n ) f(n) f(n) 這個函式的呼叫次數，如圖所示：

??觀察 c [ n ] c[n] c[n] 的增長趨勢，首先排除等引數列，然后再來看是否符合等比數列，我們來嘗試求下 c [ n ] / c [ n ? 1 ] c[n] / c[n-1] c[n]/c[n?1] 的值，列出表格如下：

??觀察發現，隨著 n n n 的不斷增大， c [ n ] / c [ n ? 1 ] c[n]/c[n-1] c[n]/c[n?1] 越來越接近一個常數，而這個常數就是黃金分割的倒數： 2 5 ? 1 ≈ 1.618034 \frac {2}{ \sqrt 5 - 1} \approx 1.618034 5 ??12?≈1.618034??當 n n n 趨近于無窮大的時候，滿足如下公式： c [ n ] = 2 5 ? 1 c [ n ? 1 ] c[n] = \frac {2}{ \sqrt 5 - 1} c[n-1] c[n]=5 ??12?c[n?1]??對等比數列化解后累乘得到： c [ n ] = 2 5 ? 1 c [ n ? 1 ] = ( 2 5 ? 1 ) 2 c [ n ? 2 ] = ( 2 5 ? 1 ) n \begin{aligned}c[n] &= \frac {2}{ \sqrt 5 - 1} c[n-1]\\ &= (\frac {2}{ \sqrt 5 - 1})^2 c[n-2]\\ &= (\frac {2}{ \sqrt 5 - 1})^n \end{aligned} c[n]?=5 ??12?c[n?1]=(

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/300748.html

標籤：其他

上一篇：還重構？就你那代碼只能鏟了重寫！

下一篇：自動駕駛開發入門（三）---淺談Apollo Cyber RT中的Transport