資料結構與算法學習筆記

1. 資料結構與算法

1.1 知識腦圖

1.2 什麼是 資料結構 與 算法

• 資料結構 就是一組資料的存儲結構
• 算法 就是操作一組資料的方法
• 資料結構是為算法服務的，算法要作用在特定的資料結構之上

1.3 為什麼需要資料結構和算法

• 在計算機科學和網際網路迅猛發展下，需要計算的資料量越來越龐大。但是計算機的計算能力是有限的，這麼大量的資料計算，需要越來越多的計算機，需要越來越長的計算時間，注重效率的我們需要盡可能的提高計算效率
• 選用合适的資料結構和算法，特别是在處理體量非常龐大的資料的時候，可以極大提高計算效率

1.4 怎麼樣衡量資料結構和算法

• 我們需要一個不用具體的測試資料來測試，就可以粗略地估計算法的執行效率的方法
• 衡量的标準(metric) — 時間複雜度 和 空間複雜度

1.4.1 大 O 複雜度表示法

T(n) = O(f(n))
// T(n) 表示代碼執行的時間；
// n 表示資料規模的大小
// f(n) 表示每行代碼執行的次數總和,因為這是一個公式，是以用 f(n) 來表示
// O 表示代碼的執行時間 T(n) 與 f(n) 表達式成正比
           

1.4.2 時間複雜度 分析

• 大 O 時間複雜度 實際上并不具體表示代碼真正的執行時間，而是表示代碼執行時間随資料規模增長的變化趨勢，是以，也叫作漸進時間複雜度（asymptotic time complexity），簡稱時間複雜度

1.4.2.1 隻關注循環執行次數最多的一段代碼

• 大 O 這種複雜度表示方法隻是表示一種變化趨勢。我們通常會忽略掉公式中的常量、低階、系數，隻需要記錄一個最大階的量級就可以了

int cal(int n) { //1
   int sum = 0; //2
   int i = 1; //3 
   for (; i <= n; ++i) { //4
     sum = sum + i; //5
   } //6
   return sum; //7
 }
 // 其中第 2、3 行代碼都是常量級的執行時間，與 n 的大小無關，是以對于複雜度并沒有影響。循環執行次數最多的是第 4、5 行代碼，是以這塊代碼要重點分析。
 // 這兩行代碼被執行了 n 次，是以總的時間複雜度就是 O(n)
           

1.4.2.2 加法法則：總複雜度等于量級最大的那段代碼的複雜度

如果 T1(n) = O(f(n))，T2(n) = O(g(n))；
那麼 T(n) = T1(n) + T2(n) = max(O(f(n)), O(g(n))) = O(max(f(n), g(n)))
           

1.4.2.3 乘法法則：嵌套代碼的複雜度等于嵌套内外代碼複雜度的乘積

如果 T1(n) = O(f(n))，T2(n) = O(g(n))；
那麼 T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O(f(n) *  g(n))
           

1.4.2.4 常見的幾種時間複雜度分析

• 可以粗略地分為兩類，多項式量級和非多項式量級
• 其中，非多項式量級隻有兩個：O(2n) 和 O(n!)
• 當資料規模 n 越來越大時，非多項式量級算法的執行時間會急劇增加，求解問題的執行時間會無限增長。是以，非多項式時間複雜度的算法其實是非常低效的算法

1.4.2.4.1 O(1)

• O(1) 隻是常量級時間複雜度的一種表示方法，并不是指隻執行了一行代碼
• 一般情況下，隻要算法中不存在循環語句、遞歸語句，即使有成千上萬行的代碼，其時間複雜度也是Ο(1)

1.4.2.4.2 O(logn)、O(nlogn)

• 對數之間是可以互相轉換的，log3n 就等于 log32 * log2n，是以 O(log3n) = O(C * log2n)，其中 C=log32 是一個常量
• 基于我們前面的一個理論：在采用大 O 标記複雜度的時候，可以忽略系數，即 O(Cf(n)) = O(f(n))。是以，O(log2n) 就等于 O(log3n)。
• 是以，在對數階時間複雜度的表示方法裡，我們忽略對數的“底”，統一表示為 O(logn)
• 如果一段代碼的時間複雜度是 O(logn)，我們循環執行 n 遍，時間複雜度就是 O(nlogn) 了。
• O(nlogn) 也是一種非常常見的算法時間複雜度。比如，歸并排序、快速排序的時間複雜度都是 O(nlogn)

1.4.2.4.3 O(m+n)、O(m*n)

• 代碼的複雜度由兩個資料的規模來決定
• 我們無法事先評估 m 和 n 誰的量級大，是以我們在表示複雜度的時候，就不能簡單地利用加法法則，省略掉其中一個。

1.4.2.5 最好時間複雜度

• 在最理想的情況下，執行這段代碼的時間複雜度

1.4.2.6 最壞時間複雜度

• 在最糟糕的情況下，執行這段代碼的時間複雜度
• 一般情況下，我們隻需考慮最壞時間複雜度就行

1.4.2.7 平均時間複雜度

• 最好與最壞是在極端情況下發生的，平均情況複雜度引入了機率，是以也叫權重平均時間複雜度或者期望時間複雜度
• 隻有同一塊代碼在不同的情況下，時間複雜度有量級的差距，我們才會使用這最好，最壞，平均這三種複雜度表示法來區分

1.4.2.8 均攤時間複雜度

• 應用的場景特殊、有限
• 出現的頻率是非常有規律的，而且有一定的前後時序關系
• 在能夠應用均攤時間複雜度分析的場合，一般均攤時間複雜度就等于最好情況時間複雜度

1.4.3 空間複雜度 分析

• 大O空間複雜度全稱就是漸進空間複雜度（asymptotic space complexity），表示算法的存儲空間與資料規模之間的增長關系
• 是指除了原本的資料存儲空間外，算法運作還需要額外的存儲空間
• 常見的空間複雜度就是 O(1)、O(n)、O(n2)

1.5 算法概述

• 算法就是一種解析問題的思路或者說方案
• 算法沒有最好的，隻有最适合的

1.5.1 特性

• 輸入
• 輸出
• 有窮性
• 确定性
• 可行性

1.5.2 基本要求

• 正确性
• 可讀性
• 健壯性
• 時間複雜度 （運作時間越快越好）
• 空間複雜度 （占用資源越少越好）

2. 各種資料結構簡析

2.1 數組

• 是一種線性表資料結構
• 連續的記憶體空間，存儲相同類型的一組資料
• 支援随機通路（時間複雜度為O(1))
• 插入、删除操作比較低效 （時間複雜度為O(n))
• 對于業務開發，直接使用容器就足夠了，省時省力。畢竟損耗一丢丢性能，完全不會影響到系統整體的性能。
• 但如果是做一些非常底層的開發，比如開發網絡架構，性能的優化需要做到極緻，這個時候數組就會優于容器，成為首選

2.1.1 線性表

• 顧名思義，就是資料排成像一條線一樣的結構。每個線性表上的資料最多隻有前和後兩個方向

2.1.2 非線性表

• 資料之間并不是簡單的前後關系

2.1.3 連續的記憶體空間和相同類型的資料

• 這個特點 使之 具有 “随機通路” 的殺手锏
• 尋址公式：

a[k]_address = base_address + k * data_type_size

// data_type_size 表示數組中每個元素的大小
           

2.1.3.1 對 CPU 緩存更友好

• CPU 緩存是從記憶體中讀取一個資料塊（一段連續的記憶體位址），并儲存到CPU緩存中
• 下次通路記憶體資料的時候就會先從CPU緩存開始查找，如果找到就不需要再從記憶體中取。這樣就實作了比記憶體通路速度更快的機制，也就是CPU緩存存在的意義:為了彌補記憶體通路速度過慢與CPU執行速度快之間的差異而引入

2.1.4 為什麼數組的下标要從0開始，而不是1開始？

• “下标” 最确切的定義應該是 “偏移（offset）”
• 尋址公式對比：

// 下标從0開始
a[k]_address = base_address + k * data_type_size

// 下标從1開始
a[k]_address = base_address + (k - 1) * data_type_size

// data_type_size 表示數組中每個元素的大小
           

• 從 1 開始編号，每次随機通路數組元素都多了一次減法運算，對于 CPU 來說，就是多了一次減法指令,是以為了減少一次減法操作，數組選擇了從 0 開始編号，而不是從 1 開始
• 最主要的原因還是曆史原因，C 語言設計者用 0 開始計數數組下标，之後的 Java、JavaScript 等進階語言都效仿了 C 語言。
• 實際上，很多語言中數組也并不是從 0 開始計數的，比如 Matlab；Python 更是支援負數下标

2.1.5 擴充

2.1.5.1 二維數組的尋址公式

二維數組記憶體尋址：

對于 m * n 的數組，a [ i ][ j ] (i < m,j < n)的位址為：

address = base_address + (i * n + j) * data_type_size
           

2.1.5.2 C 語言中 數組越界導緻無限循環問題

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}
// 在 C 語言中，隻要不是通路受限的記憶體，所有的記憶體空間都是可以自由通路的
// 是以當i = 3 時，數組已經越界，a[3]也會被定位到某塊不屬于數組的記憶體位址上，
// 如果編譯器的記憶體配置設定是遞減的，那麼這個位址正好是存儲變量 i 的記憶體位址，那麼 a[3]=0 就相當于 i=0，是以就會導緻代碼無限循環
           

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-XYXE5sOZ-1631413187041)(https://note.youdao.com/yws/api/personal/file/3081FADEBE684E72A555E28F08A4E799?method=download&shareKey=f9123f73f012c10757490a40cbe799c7)]

2.2 連結清單

• 不需要連續的記憶體空間，通過每個節點的指針，連成一個連結清單。（通過指針将一組零散的記憶體塊（結點）串聯在一起）
• 不支援随機通路，查詢的 時間複雜度為O(n)
• 插入、删除操作比較高效 （時間複雜度為O(1))
• 單連結清單，循環連結清單，雙向連結清單

2.2.1 單連結清單

• 頭節點：第一個結點，用來記錄連結清單的基位址
• 尾節點：最後一個結點，指向一個空位址 NULL

2.2.1.1 高效的插入與删除

• 雖然單純地插入和删除的時間複雜度隻有O(1)，但查詢到指定結點的時間複雜度卻要 O(n)

2.2.2 循環連結清單

• 特殊的單連結清單
• 尾結點指針是指向連結清單的頭結點

2.2.3 雙向連結清單

• 前驅指針 prev 指向前面的結點
• 雙向連結清單可以支援 O(1) 時間複雜度的情況下找到前驅結點，正是這樣的特點，也使雙向連結清單在某些情況下的插入、删除等操作都要比單連結清單簡單、高效

2.2.3.1 删除的兩種情況

2.2.3.1.1 删除結點中“值等于某個給定值”的結點

• 這種情況，單連結清單和雙向連結清單都要周遊整個連結清單找到給定的值的結點
• 時間複雜度都為O(n)

2.2.3.1.2 删除給定指針指向的結點

• 這種情況已經找到了要删除的結點，但是删除某個結點 q 需要知道其前驅結點
• 單連結清單并不支援直接擷取前驅結點，是以，為了找到前驅結點，我們還是要從頭結點開始周遊連結清單 – O(n)
• 雙向連結清單中的結點已經儲存了前驅結點的指針，不需要像單連結清單那樣周遊 – O(1)

2.2.4 連結清單的程式設計注意事項和技巧

2.2.4.1 了解指針或引用的含義

• 不管是“指針”還是“引用”，實際上，它們的意思都是一樣的，都是存儲所指對象的記憶體位址
• 将某個變量指派給指針，實際上就是将這個變量的位址指派給指針，或者反過來說，指針中存儲了這個變量的記憶體位址，指向了這個變量，通過指針就能找到這個變量

2.2.4.2 警惕指針丢失和記憶體洩漏

• 寫連結清單代碼的時候，指針指來指去，一會兒就不知道指到哪裡了。是以，我們在寫的時候，一定注意不要弄丢了指針
• 插入結點時，一定要注意操作的順序
• 删除連結清單結點時，也一定要記得手動釋放記憶體空間

p.next = x;
x.next = p.next
// 會丢失指針，因為p.next 已經指向了 x

//應該改為下面這樣
x.next = p.next;
p.next = x;
           

2.2.4.3 利用哨兵簡化實作難度

• 針對連結清單的插入、删除操作，需要對插入第一個結點和删除最後一個結點的情況進行特殊處理
• 哨兵，解決的是國家之間的邊界問題。同理，這裡說的哨兵也是解決“邊界問題”的，不直接參與業務邏輯
• 哨兵結點是不存儲資料
• 有哨兵結點的連結清單叫帶頭連結清單

2.2.4.4 重點留意邊界條件處理

• 如果連結清單為空時，代碼是否能正常工作？
• 如果連結清單隻包含一個結點時，代碼是否能正常工作？
• 如果連結清單隻包含兩個結點時，代碼是否能正常工作？
• 代碼邏輯在處理頭結點和尾結點的時候，是否能正常工作？

2.2.5 如何基于連結清單實作 LRU 緩存淘汰算法

• LRU (最近最少使用 Least Recently Used)
• 思路：維護一個有序單連結清單，越靠近連結清單尾部的結點是越早之前通路的。當有一個新的資料被通路時，從連結清單頭開始順序周遊連結清單
• 1. 如果此資料之前已經被緩存在連結清單中了，我們周遊得到這個資料對應的結點，并将其從原來的位置删除，然後再插入到連結清單的頭部
• 2. 如果此資料沒有在緩存連結清單中，又可以分為兩種情況
• 如果此時緩存未滿，則将此結點直接插入到連結清單的頭部
• 如果此時緩存已滿，則連結清單尾結點删除，将新的資料結點插傳入連結表的頭部
• 時間複雜度為O(n)，引入散清單後，記錄每個資料的位置，可将時間複雜度降為O(1)

2.2.5.1 擴充：基于數組怎麼實作 LRU 緩存淘汰算法？

• 思路1：首位置儲存最新通路資料，末尾位置優先清理
• 當有新資料通路時：
• 如果在緩存中，那麼将找到數組中對應的資料删除掉，并将新資料插入到數組第一個位置。這個操作，數組中的資料都要往後移動一位，複雜度為O(n);
• 如果不在緩存中：
• 緩存未滿，直接将新資料插入到數組第一個位置即可，數組中的資料都要往後移動一位，複雜度O(n)
• 緩存已滿，将數組尾部資料删除掉，将新資料插入到數組第一個位置，數組中的資料都要往後移動一位，複雜度O(n)
• 思路2：末尾位置儲存最新通路資料，首位置優先清理
• 當有新資料通路時：
• 如果在緩存中，那麼将找到數組中對應的資料删除掉，并将新資料插入到數組末尾，這個操作，數組中的資料都要往前移動一位，複雜度為O(n);
• 如果不在緩存中：
• 緩存未滿，直接将新資料插入到數組末尾位置即可，數組中的資料都要往後移動一位，複雜度O(n)
• 緩存已滿，将數組第一個資料删除掉，數組中的資料都要往前移動一位，将新資料插入到數組第末尾位置，複雜度O(n)

2.2.6 如果字元串是通過單連結清單來存儲的，那該如何來判斷該字元串是一個回文串？

• 回文串又稱為“水仙花字元串”，比如 “上海自來水來自海上”
• 回文的核心就是對稱，是以關鍵是找到對稱點
• 思路一：以空間換時間
• 周遊連結清單，将連結清單中的字元倒序存儲一份在另一個連結清單中
• 同時周遊兩個連結清單，對比兩個連結清單中字元，如果相等就是回文，不相等就不是。
• 時間複雜度O(n)，空間複雜度O(n)
• 思路二：快慢指針法
• 快指針 每步走兩步，慢指針 每步走一步，并且每走一步将連結清單反向
• 當快指針走到末尾時，慢指針剛好到中心對稱點
• 然後再增加一個指針，從中心點往回走（因為前半部分已經反向），慢指針接着往後走，并比較每一步的值
• 如果相等就說明是，不相等就不是
• 時間複雜度O(n)，空間複雜度O(1)(因為沒有額外增加空間，隻是多了3個輔助的指針而已)

2.3 棧

• 棧是一種 “操作受限”的線性表，隻允許在一端插入和删除資料
• 當某個資料集合隻涉及在一端插入和删除資料，并且滿足 後進先出、先進後出 的特性，我們就應該首選“棧”這種資料結構
• 用數組實作的棧，我們叫作順序棧
• 用連結清單實作的棧，我們叫作鍊式棧

2.3.1 棧的應用

2.3.1.1 棧在函數調用中的應用 —— 函數調用棧

• 作業系統給每個線程配置設定了一塊獨立的記憶體空間，這塊記憶體被組織成“棧”這種結構, 用來存儲函數調用時的臨時變量
• 每進入一個函數，就會将臨時變量作為一個棧幀入棧，
• 當被調用函數執行完成，傳回之後，将這個函數對應的棧幀出棧

int main() {
   int a = 1; 
   int ret = 0;
   int res = 0;
   ret = add(3, 5);
   res = a + ret;
   printf("%d", res);
   reuturn 0;
}

int add(int x, int y) {
   int sum = 0;
   sum = x + y;
   return sum;
}
           

2.3.1.2 棧在表達式求值中的應用

• 編譯器就是通過兩個棧來實作的。
• 其中一個儲存操作數的棧，另一個是儲存運算符的棧。
• 從左向右周遊表達式，當遇到數字，我們就直接壓入操作數棧；當遇到運算符，就與運算符棧的棧頂元素進行比較
• 如果比運算符棧頂元素的優先級高，就将目前運算符壓入棧
• 如果比運算符棧頂元素的優先級低或者相同，從運算符棧中取棧頂運算符，從操作數棧的棧頂取 2 個操作數，然後進行計算，再把計算完的結果壓入操作數棧，繼續比較

2.3.1.3 棧在括号比對中的作用

• 用棧來儲存未比對的左括号，從左到右依次掃描字元串。
• 當掃描到左括号時，則将其壓入棧中；當掃描到右括号時，從棧頂取出一個左括号。如果能夠比對，比如“(”跟“)”比對，“[”跟“]”比對，“{”跟“}”比對，則繼續掃描剩下的字元串。
• 如果掃描的過程中，遇到不能配對的右括号，或者棧中沒有資料，則說明為非法格式。
• 當所有的括号都掃描完成之後，如果棧為空，則說明字元串為合法格式；否則，說明有未比對的左括号，為非法格式。

2.3.2 為什麼函數調用要用“棧”來儲存臨時變量呢？用其他資料結構不行嗎？

• 因為棧的 “先進後出”的特性 剛好符合函數臨時變量的作用域（隻要能保證每進入一個新的函數，都是一個新的作用域就可以。而要實作這個，用棧就非常友善。在進入被調用函數的時候，配置設定一段棧空間給這個函數的變量，在函數結束的時候，将棧頂複位，正好回到調用函數的作用域内）
• 原則上 隻要符合 函數臨時變量的作用域的資料結構，都可以用來儲存臨時變量。棧可以用數組和連結清單來實作。

2.3.3 JVM 裡面的“棧”跟我們這裡說的“棧”是不是一回事呢？

• 嚴格來說 不是一回事，JVM 的棧是作業系統的一段虛拟記憶體，而 通常說的“棧” 是一種抽象的資料結構
• 但總體來說，也可以說是一樣的，他們都符合棧的特性。

2.4 隊列

• 先進先出，後進後出
• 順序隊列：數組實作，可以實作一個有界隊列（bounded queue）
• 鍊式隊列：連結清單實作，可以實作一個支援無限排隊的無界隊列（unbounded queue）

2.4.1 循環隊列

• 顧名思義它長的像一個環

  

• 要想寫出沒有 bug 的循環隊列的實作代碼，最關鍵的是，确定好隊空和隊滿的判定條件

在用數組實作的
非循環隊列中:
    隊滿的判斷條件是 tail == n，
    隊空的判斷條件是 head == tail
循環隊列：
    隊滿的判斷條件是 (tail+1)%n=head，
    隊空的判斷條件是 head == tail
           

• 當隊列滿時，圖中的 tail 指向的位置實際上是沒有存儲資料的。是以，循環隊列會浪費一個數組的存儲空間

  

2.4.2 阻塞隊列

• 其實就是在隊列基礎上增加了阻塞操作。
• 簡單來說，就是在隊列為空的時候，從隊頭取資料會被阻塞。因為此時還沒有資料可取，直到隊列中有了資料才能傳回；
• 如果隊列已經滿了，那麼插入資料的操作就會被阻塞，直到隊列中有空閑位置後再插入資料，然後再傳回
• 用阻塞隊列 可以 實作 “生産者-消費者”模式

2.4.3 并發隊列

• 就是線程安全的隊列
• 最簡單直接的實作方式是直接在 enqueue()、dequeue() 方法上加鎖，但是鎖粒度大并發度會比較低，同一時刻僅允許一個存或者取操作。
• 基于數組的循環隊列，利用 CAS 原子操作，可以實作非常高效的并發隊列

在入隊前，擷取tail位置，
入隊時比較tail是否發生變化，如果否，則允許入隊，反之，本次入隊失敗。
出隊則是擷取head位置，進行cas
           

3. 遞歸 （Recursion）-- 是一種非常高效、簡潔的程式設計技巧

3.1 概念

• 函數調用自身，稱為遞歸

3.2 遞歸需要滿足的三個條件

• 3.2.1 一個問題的解可以分解為幾個子問題的解
• 3.2.2 這個問題與分解後的子問題，除了資料規模不同，求解思路完全一樣
• 3.2.3 存在遞歸終止條件

3.3 如何了解和編寫遞歸代碼

• 找到如何将大問題分解為小問題的規律
• 基于規律寫出遞歸公式
• 推敲出終止條件
• 最後将遞歸公式和終止條件翻譯成代碼
• 不用想一層層的調用關系，不要試圖用人腦去分解遞歸的每個步驟

3.4 遞歸的弊端及其避免

3.4.1 警惕堆棧的溢出

• 1.不要遞歸太深，超過一定深度時，直接傳回報錯
• 2.使用尾遞歸
• 3.用疊代循環換掉遞歸

3.4.2 警惕重複計算

• 通過一個資料結構（比如散清單）來儲存已求解過的f(k)。當遞歸調用到f(k)時，先看下是否已經求解過，如果是，則直接從散清單中取值傳回，不需要重複計算

3.5 尾遞歸

3.5.1 尾調用

• 某個函數的最後一步是調用另一個函數

function f(x) {
    return g(x);
}
           

3.5.1.1 尾調用優化

• 函數調用會在記憶體中形成一個“調用幀”，儲存調用位置和内部變量等資訊
• 尾調用由于是函數的最後一步操作，是以不需要保留外層函數的調用記錄，隻要直接用内層函數的調用記錄就可以
• 這樣将大大節省記憶體，這就是“尾調用優化”的意義。

3.5.2 尾遞歸概念

• 如果尾調用自身，并且return語句不能包含表達式，就稱為尾遞歸

3.5.2.1 尾遞歸優化

• 确定是尾遞歸後，編譯器或者解釋器可以把尾遞歸做優化，是遞歸無論調用多少次，都隻占用一個棧幀，不會出現棧溢出的現象
• java，js等是支援尾遞歸優化的
• 普通遞歸，例如：n的階乘

//每次都要儲存調用資訊，空間複雜度 O(n)
function fastorial(n) {
    if (n === 1) {
        return n;
    }
    return n * fastorial(n-1);
}
           

• 尾遞歸

//隻需要保留最後一個調用記錄，空間複雜度 O(1)
function fastorial(n，total) {
    if (n === 1) {
        return total;
    }
    return fastorial(n-1,n*total);
}
           

4. 排序

• 原地排序：特指空間複雜度為O(1)的排序算法
• 穩定排序：相等元素的原有先後順序不變
• 有序度：數組中具有有序性（升序）的元素的對數

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

• 滿有序度：完全有序的數組的有序度，等于 n*(n-1)/2
• 逆序度：數組中具有無序性（降序）的元素的對數，與有序度剛好相反。逆序度 = 滿有序度 - 有序度

4.1 冒泡排序（BubbleSort）

• 冒泡：最大/小的先冒出來
• 相鄰的兩個數相比較，每次排序都會将一個數放到合适的位置
• 時間複雜度：O(n2)
• 空間複雜度：O(1)
• 是一種穩定的，原地排序算法

/** 用數組實作*/
public static void bubbleSort (int[] arr) {
        if (Objects.isNull(arr) || arr.length <= 1) {
            return;
        }
        int size = arr.length;
        for (int i = 0;i < size;i++) {
//            for (int j = i+1;j < size;j++) {
//                if (arr[i] > arr[j]) {
//                    int temp = arr[i];
//                    arr[i] = arr[j];
//                    arr[j] = temp;
//                }
//            }
            //提前退出冒泡循環的标記位
            boolean flag = false;
            for (int j = 0;j < size - i - 1;j++) {
                if (arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    //說明發生了交換
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
    }
    
/** 用連結清單實作*/
class Node {
    int value;
    Node next;
    Node(int value) {
        this.value = value;
    }
    
    @Override
    public String toString() {
        if (this.next == null) {
            return String.valueOf(this.value);
        }
        return this.value + "->" + this.next.toString();
    }
}

//方法一，交換節點的值 （一般情況下 不允許）
public Node bubbleSort1 (Node head) {
    if (head == null) {
        return head;
    }
    Node temp = head;
    int len = 0;
    //擷取數組的長度
    while (temp != null) {
        temp = temp.next;
        len++;
    }
    for (int i = 0;i < len;i++) {
        Node current = head;
        boolean flag = false;
        for (j = 0;i < len - i - 1;j++) {
            if (current.value > current.next.value) {
                //交換值
                int tempValue = current.value;
                current.value = current.next.value;
                current.next.value = temp;
                flag = true;
            }
            current = current.next;
        }
        if (!flag) {
            break;
        }
    }
    return head;
    
}

//方法二，交換節點指針
public Node bubbleSort2 (Node head) {
    if (head == null) {
        return head;
    }
    Node temp = head;
    int len = 0;
    //擷取連結清單的長度
    while (temp != null) {
        temp = temp.next;
        len++;
    }
    // 緩存新連結清單頭結點
    Node newHead = head;
    
    for (int i = 0;i < len;i++) {
        //每次循環都是冒泡一次的連結清單
        Node current = newHead;
        Node pre = null;
        boolean flag = false;
        for (j = 0;i < len - i - 1;j++) {
            if (current.value > current.next.value) {
               //1、交換兩個節點的引用，此時current的指針交換後會前移，隻需要更新pre指向即可
               
               //緩存下下個節點
               Node tempNode = current.next.next;
               
               //下個節點 指向目前節點  反向
               current.next.next = current;
               
               //前一個節點指向 current.next
               if (pre != null) {
                   pre.next = current.next;
               } else { //說明目前節點為頭節點，那麼更新頭節點
                   newHead = current.next;
               }
               //前節點相應後移一位
               pre = current.next;
               //目前節點指向下下個節點
               current.next = tempNdoe;
               flag = true;
            } else {
                pre = current;
                current = current.next;
            }
            
        }
        if (!flag) {
            break;
        }
    }
    return head;
    
}
           

4.2 插入排序

• 将要排序的數組，分成 已排序區間 和 未排序區間；初始的已排序區間隻有第一個元素
• 取未排序區間的元素，插入到已排序區間中，并保證已排序區間的資料一直有序
• 重複這個過程，直到未排序區間中元素個數為空
• 時間複雜度：O(n2)
• 空間複雜度：O(1)
• 是一種穩定的，原地排序算法

public static void insertionSort (int[] arr) {
        if (Objects.isNull(arr) || arr.length <= 1) {
            return;
        }
        for (int i = 1;i < arr.length;i++) {
            int temp = arr[i];
            int j = i - 1;
            for (;j >= 0;j--) {
                if (arr[j] > temp) {
                    //将大于temp的值，後移一位；交換資料
                    arr[j+1] = arr[j];
                } else {
                    break;
                }
            }
            //插入資料
            arr[j+1] = temp;
        }
    }
           

4.3 選擇排序

• 将要排序的數組，分成 已排序區間 和 未排序區間；初始的已排序區間沒有元素
• 從未排序區間中找到最小的元素，将其放到已排序區間的末尾
• 重複這個過程，直到未排序區間中元素個數為空
• 時間複雜度：O(n2)
• 空間複雜度：O(1)
• 是一種不穩定的，原地排序算法

public static void selectionSort (int[] arr) {
        if (Objects.isNull(arr) || arr.length <= 1) {
            return;
        }
        //找到未排序空間的最小值的索引
        for (int i = 0;i < arr.length;i++) {
            int least = i;
            for (int j = i+1;j < arr.length;j++) {
                if (arr[j] < arr[i]) {
                    least = j;
                }
            }
            //将最小值放到排序空間的末尾（與排序空間的最後一個元素交換位置）
            int temp = arr[i];
            arr[i] = arr[least];
            arr[least] = temp;
        }
    }
           

4.4 歸并排序

• 分治思想，先分解後合并
• 分解：将要排序的數組，從中間分成兩部分，然後對兩部分分别進行排序；以此類推，直到不能分為止。（利用遞歸實作）
• 合并：将排好序的兩部分，合并成一個排好序的新數組）
• 時間複雜度：O(nlogn)
• 空間複雜度：O(n) 因為合并時，新增了一個長度為n的數組
• 是一種穩定的，非原地排序算法

public static void mergeSort (int a[]) {
        if (a != null) {
            int len = a.length;
            mergeDivide(a,0,len-1);
        }
    }

    private static void mergeDivide (int[] a,int p,int r) {
        //遞歸終止條件
        if (p >= r) {
            return;
        }
        // 取p到r之間的中間位置q
        int q = p + (r-p)/2;
        // 分治遞歸
        mergeDivide(a,p,q);
        mergeDivide(a,q+1,r);
        // 合并
       // merge(a,p,q,r);
        merge2(a,p,q,r);
    }

    // 不帶哨兵模式
    private static void merge (int[] a,int p, int q,int r) {
        //申請一個與a同樣大小的臨時數組
        int[] temp = new int[r - p + 1];
        int i = p;
        int j = q+1;
        int k = 0;
        while (i <= q && j <= r) {
            if (a[i] <= a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }
        //判斷哪個子數組還有剩餘的資料
        int start = i;
        int end = q;
        if (j <= r) {
            start = j;
            end = r;
        }
        // 将剩餘的資料拷貝到臨時數組tmp
        while (start <= end) {
            temp[k++] = a[start++];
        }
        // 将tmp中的數組拷貝回a[p...r]
        for (int m = 0;m <= r-p;m++) {
            a[p+m] = temp[m];
        }
    }

    // 哨兵模式
    private static void merge2 (int[] a,int p, int q,int r) {
        //申請左右兩個臨時數組
        int[] left = new int[q - p + 2];
        int[] right = new int[r - q + 1];
        int leftMax = left.length - 1;
        int rightMax = right.length - 1;
        for (int i = 0;i < leftMax;i++) {
            left[i] = a[p+i];
        }
        for (int i = 0;i < rightMax;i++) {
            right[i] = a[q+1+i];
        }
        left[leftMax] = Integer.MAX_VALUE;
        right[rightMax] = Integer.MAX_VALUE;
        //比較大小，把有序資料放回原數組 利用哨兵簡化，如果左右部分的最後一個元素都是最大且相等，左邊結束時右邊也已經結束
        //不帶哨兵的遞歸是比較過後，把有序資料放入temp數組
        int i = 0;
        int j = 0;
        int k = p;
        while (k <= r) {
            if (left[i] < right[j]) {
                a[k++] = left[i++];
            } else {
                a[k++] = right[j++];
            }
        }
    }
           

4.5 快速排序

• 分治思想，先分區然後處理每個分區
• 随機選擇要排序數組的一個資料作為分區點pv（一般取數組的最後一個元素為分區點），然後将小于pv的放到左邊，大于pv的放到右邊。重複這個步驟，直到無法分區
• 核心是分區函數其實作類似與選擇排序
• 時間複雜度：O(nlogn)
• 空間複雜度：O(1)
• 是一種不穩定的，原地排序算法

public static void quickSort(int[] a,int left,int right) {
        if (left >= right) {
            return;
        }
        //進行分區，并傳回分區後中心點的索引值
        int middle = partition(a,left,right);

        //遞歸 分區
        quickSort(a,left,middle-1);
        quickSort(a,middle + 1,right);
    }

    private static int partition (int[] a,int left,int right) {
        //選擇最後一個為分區點
        int pivot = a[right];
        //i-1為已處理區間 -- 比pivot小
        int i = left;
        //j為未處理區間，從其中找出比pivot小的數值，與已處理區間末尾的資料（比pivot大）交換
        for (int j = left;j < right;j++) {
            if (a[j] < pivot) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                i++;
            }
        }
        //将pivot 放到 中間 （已處理區間末尾）
        int temp = a[i];
        a[i] = pivot;
        a[right] = temp;
        return i;
    }
           

4.6 歸并排序與快排都用了分治算法的思想，他們的差別在哪？

• 歸并排序：由下到上的，先處理子問題，然後再合并
• 快速排序：由上而下的，先分區，然後再處理子問題

4.6.1 有10個300M的日志檔案，每個檔案裡面的每行資料都按時間戳升序排好序，現在要将其合并為一個檔案，并且要求檔案的資料還是按時間戳升序，此時機器記憶體隻有1G，該怎麼解決？

• 開10個檔案通道，初始每個通道加載100M的日志到記憶體，充分利用記憶體，實作高速讀寫（當然為了考慮到實際因素，可留200M記憶體，給伺服器其他程式用，每個通道加載80M的資料）
• 建立一個數組，容量為10，讀取記憶體中每個檔案的首位記錄，放入數組并升序排序
• 取數組首位記錄，寫入新檔案
• 從數組首位記錄所屬檔案讀取首位記錄，使用二分查找插入有序數組
• 重複步驟三
• 如果記憶體中的某個檔案記憶體記錄讀取完畢，則周遊所有檔案記憶體，從磁盤中加載日志記錄到記憶體，保持每個檔案100M記憶體記錄，直至整個檔案讀取完畢

4.7 線性排序

• 線性排序算法的時間複雜度為O(n)
• 線性排序算法的空間複雜度為O(n)，以空間換時間
• 線性排序算法基本都不涉及元素之間的比較操作，是非基于比較的排序算法。
• 對排序資料的要求很苛刻，重點掌握此線性排序算法的适用場景

4.7.1 桶排序

4.7.1.1 算法原理：

• 将要排序的資料分到幾個有序的桶裡，每個桶裡的資料再單獨進行快速排序。
• 桶内排完序之後，再把每個桶裡的資料按照順序依次取出，組成的序列就是有序的了。

4.7.1.2 使用條件

• 要排序的資料需要很容易就能劃分成m個桶，并且桶與桶之間有着天然的大小順序。
• 資料在各個桶之間分布是均勻的。

4.7.1.3 适用場景

• 桶排序比較适合用在外部排序中。
• 外部排序就是資料存儲在外部磁盤且資料量大，但記憶體有限無法将整個資料全部加載到記憶體中。

4.7.1.4 應用案例

• 需求描述：

• 有10GB的訂單資料，需按訂單金額（假設金額都是正整數）進行排序

  但記憶體有限，僅幾百MB

• 解決思路：
• 掃描一遍檔案，看訂單金額所處資料範圍，比如1元-10萬元，那麼就分100個桶。
• 第一個桶存儲金額1-1000元之内的訂單，第二個桶存1001-2000元之内的訂單，依次類推。
• 每個桶對應一個檔案，并按照金額範圍的大小順序編号命名（00，01，02，…，99）。
• 将100個小檔案依次放入記憶體并用快排排序。
• 所有檔案排好序後，隻需按照檔案編号從小到大依次讀取每個小檔案并寫到大檔案中即可。
• 注意點：若單個檔案無法全部載入記憶體，則針對該檔案繼續按照前面的思路進行處理即可

4.7.2 計數排序（Counting sort）

4.7.2.1 算法原理

• 計數其實就是桶排序的一種特殊情況。
• 當要排序的n個資料所處範圍并不大時，比如最大值為k，則分成k個桶
• 每個桶内的資料值都是相同的，就省掉了桶内排序的時間

4.7.2.2 計數排序的關鍵步驟

• 步驟一：掃描待排序資料arr[N]，使用計數數組counting[MAX-MIN]，對每一個arr[N]中出現的元素進行計數；
• 步驟二：掃描計數數組counting[]，還原arr[N]，排序結束；

4.7.2.3 案例分析：

• 假設待排序的數組，arr={5, 3, 7, 1, 8, 2, 9, 4, 7, 2, 6, 6, 2, 6, 6}

  很容易發現，待排序的元素在[0, 10]之間，可以用counting[0,10]來存儲計數

• 第一步：統計計數

  

• 第二步：還原數組

  

4.7.2.4 使用條件

• 隻能用在資料範圍不大的場景中，若資料範圍k比要排序的資料n大很多，就不适合用計數排序；
• 計數排序隻能給非負整數排序，其他類型需要在不改變相對大小情況下，轉換為非負整數；
• 比如如果考試成績精确到小數後一位，就需要将所有分數乘以10，轉換為整數。

4.7.3 基數排序（Radix sort）

• 先以個位數的大小來對資料進行排序，接着以十位數的大小來多數進行排序，接着以百位數的大小……
• 排到最後，就是一組有序的元素了

4.7.3.1 算法原理（以排序10萬個手機号為例來說明）

• 比較兩個手機号碼a，b的大小，如果在前面幾位中a已經比b大了，那後面幾位就不用看了。
• 借助穩定排序算法的思想，可以先按照最後一位來排序手機号碼，然後再按照倒數第二位來重新排序，以此類推，最後按照第一個位重新排序。
• 經過11次排序後，手機号碼就變為有序的了。
• 每次排序有序資料範圍較小，可以使用桶排序或計數排序來完成。

4.7.3.2 使用條件

• 要求資料可以分割獨立的“位”來比較；
• 位之間由遞進關系，如果a資料的高位比b資料大，那麼剩下的地位就不用比較了；
• 每一位的資料範圍不能太大，要可以用線性排序，否則基數排序的時間複雜度無法做到O(n)。

4.7.5 思考

4.7.5.1 如何根據年齡給100萬使用者資料排序？

• 利用桶排序
• 假設年齡的範圍最小 1 歲，最大不超過 120 歲。
• 我們可以周遊這 100 萬使用者，根據年齡将其劃分到這 120 個桶裡，然後依次順序周遊這 120 個桶中的元素

4.7.5.2 對D，a，F，B，c，A，z這幾個字元串進行排序，要求将其中所有小寫字母都排在大寫字母前面，但是小寫字母内部和大寫字母内部不要求有序。比如經過排序後為a，c，z，D，F，B，A，這個如何實作呢？如果字元串中處理大小寫，還有數字，将數字放在最前面，又該如何解決呢？

• 利用桶排序思想，弄小寫，大寫，數字三個桶，周遊一遍，都放進去，然後再從桶中取出來就行了

5. 二分查找

• 二分查找針對的是一個有序的資料集合，每次通過跟區間中間的元素對比，将待查找的區間縮小為之前的一半，直到找到要查找的元素，或者區間縮小為0

5.1 二分查找的時間複雜度 – O(logN)

• 假設資料大小是n，每次查找後資料都會縮小為原來的一半，最壞的情況下，直到查找區間被縮小為空，才停止。
• 是以，每次查找的資料大小是：n，n/2，n/4，…，n/(2k)，…，這是一個等比數列。當n/(2k)=1時，k的值就是總共縮小的次數，也是查找的總次數。而每次縮小操作隻涉及兩個資料的大小比較，是以，經過k次區間縮小操作，時間複雜度就是O(k)。通過n/(2^k)=1，可求得k=log2n，是以時間複雜度是O(logn)

5.1.1 認識O(logN)

• 這是一種極其高效的時間複雜度，有時甚至比O(1)的算法還要高效(因為大O表示法，是忽略了常數的，假如這個常數比較大時，比如 10000,這時O(logN)更高效)
• 因為logn是一個非常“恐怖“的數量級，即便n非常大，對應的logn也很小。比如n等于2的32次方，也就是42億，而logn才32

5.2 二分查找的實作

5.2.1 簡單二分查找的實作

• 資料中沒有重複元素

5.2.1.1 循環

public int binarySearch (int[] a,int val) {
    int start = 0;
    int end = a.length - 1;
    while (start <= end) {
        int mid = start + ((end-start) >> 1); // start + (end - start) / 2
        
        if (a[mid] > val) {
            end = mid - 1;
        } else if (a[mid] < val) {
            start = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}
           

5.2.1.1.1 注意事項

• 循環退出條件是：start<=end，而不是start<end。
• mid的取值，使用mid=start + (end - start) / 2，而不用mid=(start + end)/2，因為如果start和end比較大的話，求和可能會發生int類型的值超出最大範圍。為了把性能優化到極緻，可以将除以2轉換成位運算，即start + ((end - start) >> 1)，因為相比除法運算來說，計算機處理位運算要快得多
• start和end的更新：start = mid - 1，end = mid + 1，若直接寫成start = mid，end=mid，就可能會發生死循環

5.2.1.2 遞歸

public int binarySearch (int[] a,int val) {
    return subBinarySearch(a,val,0,a.length - 1);
}

private int subBinarySearch (int[] a,int val,int start,int end) {
    if (start > end) {
        return -1;
    }
    int mid = start + ((end - start) >> 1);
    if (a[mid] > val) {
        end = mid -1;
    } else if (a[mid] < val) {
        start = mid + 1;
    } else {
        return mid;
    }
    return subBinarySearch(a,val,start,end);
}
           

5.2.2 四種常見的二分查找變形問題實作

5.2.2.1 查找第一個等于給定值的元素

public int binarySearch (int[] a,int val) {
    int start = 0;
    int end = a.length - 1;
    while (start <= end) {
        int mid = start + ((end-start) >> 1); // start + (end - start) / 2
        
        if (a[mid] > val) {
            end = mid - 1;
        } else if (a[mid] < val) {
            start = mid + 1;
        } else {
            if ((mid == 0) || (a[mid-1]) != val) {
                return mid;
            } else {
                 end = mid - 1;
            }
        }
    }
    return -1;
}
           

5.2.2.2 查找最後一個等于給定值的元素

public int binarySearch (int[] a,int val) {
    int start = 0;
    int end = a.length - 1;
    while (start <= end) {
        int mid = start + ((end-start) >> 1); // start + (end - start) / 2
        
        if (a[mid] > val) {
            end = mid - 1;
        } else if (a[mid] < val) {
            start = mid + 1;
        } else {
            if ((mid == a.length - 1) || (a[mid+1]) != val) {
                return mid;
            } else {
                start = mid + 1;
            }
        }
    }
    return -1;
}
           

5.2.2.3 查找第一個大于等于給定值的元素

public int binarySearch (int[] a,int val) {
    int start = 0;
    int end = a.length - 1;
    while (start <= end) {
        int mid = start + ((end-start) >> 1); // start + (end - start) / 2
        
        if (a[mid] >= val) {
            if ((mid == 0) || (a[mid-1]) < val) {
                return mid;
            } else {
                end = mid - 1;
            }
        } else {
            start = mid + 1;
        }
    }
    return -1;
}
           

5.2.2.4 查找最後一個小于等于給定值的元素

public int binarySearch (int[] a,int val) {
    int start = 0;
    int end = a.length - 1;
    while (start <= end) {
        int mid = start + ((end-start) >> 1); // start + (end - start) / 2
        
        if (a[mid] <= val) {
            if ((mid == a.length - 1) || (a[mid+1]) > val) {
                return mid;
            } else {
                start = mid + 1;
            }
        } else {
            end = mid - 1;
        }
    }
    return -1;
}
           

5.3 使用條件（應用場景的局限性）

• 二分查找依賴的是順序表結構，即數組
• 二分查找針對的是有序資料，是以隻能用在插入、删除操作不頻繁，一次排序多次查找的場景中 (也就是說最适用于靜态資料)
• 資料量太小不适合二分查找，與直接周遊相比效率提升不明顯。但有一個例外，就是資料之間的比較操作非常費時，比如數組中存儲的都是長度超過300的字元串，那這是還是盡量減少比較操作使用二分查找吧。
• 資料量太大也不是适合用二分查找，因為數組需要連續的空間，若資料量太大，往往找不到存儲如此大規模資料的連續記憶體空間
• 凡是用二分查找能解決的，絕大部分我們更傾向于用散清單或者二叉查找樹。即便是二分查找在記憶體使用上更節省，但是畢竟記憶體如此緊缺的情況并不多。
• 二分查找更适合用在“近似”查找問題，在這類問題上，二分查找的優勢更加明顯

5.4 思考

5.4.1 如何在1000萬個整數中快速查找某個整數？

• 1000萬個整數占用存儲空間為40MB，占用空間不大，是以可以全部加載到記憶體中進行處理
• 用一個1000萬個元素的數組存儲，然後使用快排進行升序排序，時間複雜度為O(nlogn)
• 在有序數組中使用二分查找算法進行查找，時間複雜度為O(logn)
• 如果資料量達到百億，千億級，就用 “布隆過濾器”

5.4.2 如果二分查找的資料，使用連結清單存儲，時間的複雜度是多少？

• O(n)
• 假設連結清單長度為n，二分查找每次都要找到中間點(計算中忽略奇偶數差異):
• 第一次查找中間點，需要移動指針n/2次；
• 第二次，需要移動指針n/4次；
• 第三次需要移動指針n/8次 …,以此類推，直到一次為止

• 總共指針移動次數(查找次數) = n/2 + n/4 + n/8 + …+ 1，這顯然是個等比數列，根據等比數列求和公式：Sum = n - 1.

  最後算法時間複雜度是：O(n-1)，忽略常數，記為O(n)，時間複雜度和順序查找時間複雜度相同

5.4.3 如何程式設計實作“求一個數的平方根”？要求精确到小數點後6位？

//precision 精确度，6位的話，就是0.000001
public static double sqrt (double num,double precision) {
    if (num < 0) {
        return Double.NaN;
    }
    double low = 0;
    double up = num;
    
    if (num > 0 && num < 1) {
        low = num;
        up = 1;
    }
    
    double mid = low + (up - low) / 2;
    
    while (up - low > precision) {
        if (mid > num / mid) { //mid * mid > num 避免溢出，可以寫為 mid > num / mid
            up = mid;
        } else if (mid < num / mid) {
            low = mid;
        } else {
            return mid;
        }
        mid = low + (up - low) / 2;
    }
    
    return up;
}
           

5.4.4 如果有序數組是一個循環有序數組（暫定無重複數值），比如 4，5，6，1，2，3。針對這種情況，如何實作一個求“值等于給定值”的二分查找算法呢？

• 思路：
• 1. 找到分界下标，分成兩個有序數組
• 1. 判斷目标值在哪個有序資料範圍内，做二分查找
• 具體方案：
• 循環數組存在一個性質：以數組中間點為分區，會将數組分成一個有序數組和一個循環有序數組。
• 如果首元素小于 mid元素，說明前半部分是有序的，後半部分是循環有序數組；
• 如果首元素大于 mid元素，說明後半部分是有序的，前半部分是循環有序的數組；
• 如果目标元素在有序數組範圍中，使用二分查找；
• 如果目标元素在循環有序數組中，設定數組邊界後，使用以上方法繼續查找

class Solution {
    public int search(int[] nums, int target) {
        if (null == nums || nums.length == 0) {
            return -1;
        }
        if (nums.length == 1) {
            if (nums[0] == target) {
                return 0;
            }
            return -1;
        }
        int low = 0;
        int up = nums.length - 1;
        int index = getIndex(nums,low,up);
        if (index != -1) {
            int val = binarySearch(nums,target,low,index);
            if (val != -1) {
                return val;
            }
            return  binarySearch(nums,target,index + 1,up);
        }
        return binarySearch(nums,target,low,up);
    }

    //查找到循環數組的中間點
    private int getIndex (int[] a,int low,int up) {
        if(a.length < 1) {
            return -1;
        }
        while (low <= up) {
            int mid = low + ((up - low) >> 1);
            if (a[mid] > a[mid+1]) {
                return mid;
            } else if (a[mid] < a[low]) {
                up = mid;
            } else if (a[mid] > a[up]) {
                low = mid;
            } else {
                return -1;
            }
        }
        return -1;
    }

    //二分查找
    private int binarySearch (int[] a,int val,int low,int up) {
        while (low <= up) {
            int mid = low + ((up - low) >> 1);
            if (a[mid] > val) {
                up = mid - 1;
            } else if (a[mid] < val) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}
           

5.5 跳表 （實作了基于連結清單的“二分查找”）

• 是一種各方面性能都比較優秀的動态資料結構
• 是 連結清單加多級索引的結構
• 空間換時間

5.5.1 跳表的查詢速度 – O(logn)

• 每兩個結點會抽出一個結點作為上一級索引的結點，那第一級索引的結點個數大約就是 n/2，
• 第二級索引的結點個數大約就是 n/4，
• 第三級索引的結點個數大約就是 n/8，
• 依次類推，也就是說，第 k 級索引的結點個數是第 k-1 級索引的結點個數的 1/2，那第 k級索引結點的個數就是 n/(2k)

5.5.2 跳表是否浪費記憶體（空間複雜度） – O(n)

• 實際上，在軟體開發中，我們不必太在意索引占用的額外空間。
• 在講資料結構和算法時，我們習慣性地把要處理的資料看成整數，
• 但是在實際的軟體開發中，原始連結清單中存儲的有可能是很大的對象，
• 而索引結點隻需要存儲關鍵值和幾個指針，并不需要存儲對象，是以當對象比索引結點大很多時，那索引占用的額外空間就可以忽略了

5.5.3 高效的動态插入和删除

• 時間複雜度 都為 O(logn)
• 單純的插入操作是 O(1)，耗時主要在查詢插入的位置（單連結清單為0(n)），跳表查詢效率為O(logn)，是以整體的插入為 O(logn)
• 删除操作 同理。需要注意的是：如果删除的結點在索引中也有出現，我們除了要删除原始連結清單中的結點，還要删除索引中的

5.5.4 跳表索引動态更新

• 當不停地往跳表中插入資料時，如果我們不更新索引，就有可能出現某 2 個索引結點之間資料非常多的情況。極端情況下，跳表還會退化成單連結清單
• 作為一種動态資料結構，我們需要某種手段來維護索引與原始連結清單大小之間的平衡，也就是說，如果連結清單中結點多了，索引結點就相應地增加一些，避免複雜度退化，以及查找、插入、删除操作性能下降
• 通過随機函數來維護平衡性
• 當往跳表中插入資料的時候，我們可以選擇同時将這個資料插入到部分索引層中
• 随機函數生成了值 K，那我們就将這個結點添加到第一級到第 K 級這 K 級索引中

6 散清單

• 基本組成：Hash算法 + 數組
• • 基本上就是 HashMap （Hash算法 + 數組 + 連結清單 + 紅黑樹）

6.1 雜湊演算法的基本要求

• 散列/哈希函數計算得到的散列值是一個非負整數
• 如果 key1 = key2，那 hash(key1) == hash(key2)
• 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)，這一點無法完全滿足，是以會有哈希沖突
• 幾乎無法找到一個完美的無沖突的散列函數

6.2 解決哈希沖突

6.2.1 開放尋址法

• 線性探測Linear Probing） （如果某個資料經過散列函數散列之後，存儲位置已經被占用了，我們就從目前位置開始，依次往後查找，看是否有空閑位置，直到找到為止）
• 二次探測（Quadratic probing） 二次探測探測的步長就變成了原來的“二次方”
• 雙重散列（Double hashing） 使用一組散列函數 hash1(key)，hash2(key)，hash3(key)……我們先用第一個散列函數，如果計算得到的存儲位置已經被占用，再用第二個散列函數，依次類推，直到找到空閑的存儲位置

6.2.1.1 裝載因子

• 散清單的裝載因子=填入表中的元素個數/散清單的長度
• 裝載因子越大，說明空閑位置越少，沖突越多，散清單的性能會下降

6.2.1 連結清單法

• 所有散列值相同的元素我們都放到相同槽位對應的連結清單中

6.3 工業級哈希表的特點 – 比如 Java 中的 HashMap

• 支援快速的查詢、插入、删除操作
• 記憶體占用合理，不能浪費過多的記憶體空間
• 性能穩定，極端情況下，散清單的性能也不會退化到無法接受的情況

6.3.1 如何實作

• 設計一個合适的散列函數，不能太複雜，生成的值要盡可能随機并且均勻分布
• 定義裝載因子門檻值，并且設計動态擴容政策
• 選擇合适的散列沖突解決方法

6.4 雜湊演算法

• 将任意長度的二進制值串映射為固定長度的二進制值串（哈希值），這個映射的規則就是雜湊演算法

6.4.1 優秀雜湊演算法需要滿足的要求

• 從哈希值不能反向推導出原始資料（是以雜湊演算法也叫單向雜湊演算法）
• 對輸入資料非常敏感，哪怕原始資料隻修改了一個 Bit，最後得到的哈希值也大不相同；
• 散列沖突的機率要很小，對于不同的原始資料，哈希值相同的機率非常小；
• 雜湊演算法的執行效率要盡量高效，針對較長的文本，也能快速地計算出哈希值。

6.4.2 雜湊演算法的常見應用場景

6.4.2.1 安全加密

• MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）
• SHA（Secure Hash Algorithm，安全雜湊演算法）
• DES（Data Encryption Standard，資料加密标準）
• AES（Advanced Encryption Standard，進階加密标準）
• 即便雜湊演算法存在沖突，但是在有限的時間和資源下，雜湊演算法還是被很難破解的
• 沒有絕對安全的加密

6.4.2.1.1 鴿巢原理 / 抽屜原理

• 如果有 10 個鴿巢，有 11 隻鴿子，那肯定有 1 個鴿巢中的鴿子數量多于 1 個，換句話說就是，肯定有 2 隻鴿子在 1 個鴿巢内

6.4.2.1.2 為什麼雜湊演算法無法做到零沖突？

• 雜湊演算法産生的哈希值的長度是固定且有限的，是以能表示的資料是有限的
• 而我們要哈希的資料是無窮的
• 基于鴿巢原理，如果我們對N個資料求哈希值，就必然會存在哈希值相同的情況
• 一般情況下，哈希值越長的雜湊演算法，散列沖突的機率越低

6.4.2.2 唯一辨別

• 如果要在海量的圖庫中，搜尋一張圖是否存在
• 我們可以給每一個圖檔取一個唯一辨別，或者說資訊摘要。比如，我們可以從圖檔的二進制碼串開頭取 100 個位元組，從中間取 100 個位元組，從最後再取 100 個位元組，然後将這 300 個位元組放到一塊，通過雜湊演算法（比如 MD5），得到一個哈希字元串，用它作為圖檔的唯一辨別

6.4.2.3 資料校驗

• 用同一hash算法（比如MD5)，對檔案取哈希值并進行對比，防止資料被篡改

6.4.2.4 散列/哈希 函數

• HashMap

6.4.2.5 負載均衡

• 負載均衡算法有很多，比如輪詢、随機、權重輪詢等
• 如何才能實作一個會話粘滞（session sticky）的負載均衡算法呢？也就是說，我們需要在同一個用戶端上，在一次會話中的所有請求都路由到同一個伺服器上
• 可以通過雜湊演算法，對用戶端 IP 位址或者會話 ID 計算哈希值，将取得的哈希值與伺服器清單的大小進行取模運算，最終得到的值就是應該被路由到的伺服器編号

6.4.2.6 資料分片

6.4.2.6.1 如何統計“搜尋關鍵詞”出現的次數？

• 假如我們有 1T 的日志檔案，這裡面記錄了使用者的搜尋關鍵詞，我們想要快速統計出每個關鍵詞被搜尋的次數，該怎麼做呢？
• 我們可以先對資料進行分片，然後采用多台機器處理的方法，來提高處理速度。
• 具體的思路是這樣的：為了提高處理的速度，我們用 n 台機器并行處理。我們從搜尋記錄的日志檔案中，依次讀出每個搜尋關鍵詞，并且通過哈希函數計算哈希值，然後再跟 n 取模，最終得到的值，就是應該被配置設定到的機器編
• 這樣，哈希值相同的搜尋關鍵詞就被配置設定到了同一個機器上。也就是說，同一個搜尋關鍵詞會被配置設定到同一個機器上。每個機器會分别計算關鍵詞出現的次數，最後合并起來就是最終的結果。

6.4.2.7 分布式存儲

• 現在網際網路面對的都是海量的資料、海量的使用者。我們為了提高資料的讀取、寫入能力，一般都采用分布式的方式來存儲資料，比如分布式緩存
• 該如何決定将哪個資料放到哪個機器上呢？我們可以借用前面資料分片的思想，即通過雜湊演算法對資料取哈希值，然後對機器個數取模，這個最終值就是應該存儲的緩存機器編号
• 但是要擴容時，會有問題，由于機器增多，所有的資料都要重新計算哈希值，然後重新搬移到正确的機器上。這樣就相當于，緩存中的資料一下子就都失效了。所有的資料請求都會穿透緩存，直接去請求資料庫 — 緩存雪崩

6.4.2.7.1 一緻性雜湊演算法

• 假設我們有 k 個機器，資料的哈希值的範圍是[0, MAX]。
• 我們将整個範圍劃分成 m 個小區間（m 遠大于 k），每個機器負責 m/k 個小區間。
• 當有新機器加入的時候，我們就将某幾個小區間的資料，從原來的機器中搬移到新的機器中。
• 這樣，既不用全部重新哈希、搬移資料，也保持了各個機器上資料數量的均衡
• 具體可參考：漫畫一緻性雜湊演算法

6.5 思考題

6.5.1 為什麼哈希表和連結清單經常一塊使用？

• 哈希表這種資料結構雖然支援非常高效的資料插入、删除、查找操作，但是哈希表中的資料都是通過哈希函數打亂之後無規律存儲的。也就說，它無法支援按照某種順序快速地周遊資料。
• 如果希望按照順序周遊哈希表中的資料，那我們需要将哈希表中的資料拷貝到數組中，然後排序，再周遊
• 而且哈希表是動态資料結構，不停地有資料的插入、删除，是以每當我們希望按順序周遊散清單中的資料的時候，都需要先排序，那效率勢必會很低
• 為了解決順序快速地周遊資料效率低的問題，故經常将散清單和連結清單（或者跳表）結合在一起使用

6.5.2 假設我們有 10 萬條 URL 通路日志，如何按照通路次數給 URL 排序？

• 周遊 10 萬條資料，以 URL 為 key，通路次數為 value，存入散清單，同時記錄下通路次數的最大值 K，時間複雜度 O(N)
• 如果 K 不是很大，可以使用桶排序，時間複雜度 O(N)。
• 如果 K 非常大（比如大于 10 萬），就使用快速排序，複雜度 O(NlogN)

6.5.3 有兩個字元串數組，每個數組大約有 10萬條字元串，如何快速找出兩個數組中相同的字元串？

• 以第一個字元串數組建構散清單，key 為字元串，value 為出現次數。
• 再周遊第二個字元串數組，以字元串為 key 在散清單中查找，如果 value 大于零，說明存在相同字元串。
• 時間複雜度 O(N)

7 樹/二叉樹

7.1 樹

• A 節點就是 B 節點的父節點，B 節點是 A 節點的子節點。B、C、D 這三個節點的父節點是同一個節點，是以它們之間互稱為兄弟節點
• 根節點：把沒有父節點的節點，比如圖中的 E
• 葉子節點/葉節點：我們把沒有子節點的節點，比如圖中的 G、H、I、J、K、L
• 節點高度：節點到葉子節點的最長路徑（邊數）
• 節點深度：根節點到這個節點所經曆的的邊的個數
• 節點層數：節點深度 + 1
• 樹的高度：根節點的高度

7.2 二叉樹

• 每個節點最多有兩個“叉”，也就是兩個子節點，分别是左子節點和右子節點

7.2.1 滿二叉樹

• 葉子節點全都在最底層，除了葉子節點之外，每個節點都有左右兩個子節點
• 下圖中的2

7.2.2 完全二叉樹

• 葉子節點都在最底下兩層，最後一層的葉子節點都靠左排列(從 左數到右是連續，中間沒有斷開，缺少節點)，并且除了最後一層，其他層的節點個數都要達到最大
• 比如上圖的 編号為3的樹，以及下圖中的樹

7.2.3 二叉樹的存儲

7.2.3.1 鍊式存儲法

• 大部分二叉樹代碼都是通過這種結構來實作的

7.2.3.2 基于數組的順序存儲法

• 适合完全二叉樹
• 我們把根節點存儲在下标 i = 1 的位置，那左子節點存儲在下标 2 * i = 2 的位置，右子節點存儲在 2 * i + 1 = 3 的位置。以此類推，B 節點的左子節點存儲在 2 * i = 2 * 2 = 4 的位置，右子節點存儲在 2 * i + 1 = 2 * 2 + 1 = 5 的位置。

• 節點 X 存儲在數組中下标為 i 的位置，下标為 2 * i 的位置存儲的就是左子節點，下标為 2 * i + 1 的位置存儲的就是右子節點。
• 反過來，下标為 i/2 的位置存儲就是它的父節點
• 如果某棵二叉樹是一棵完全二叉樹，那用數組存儲無疑是最節省記憶體的一種方式。
• 因為數組的存儲方式并不需要像鍊式存儲法那樣，要存儲額外的左右子節點的指針。這也是為什麼完全二叉樹會單獨拎出來的原因，也是為什麼完全二叉樹要求最後一層的子節點都靠左的原因

7.2.4 二叉樹的周遊

• 時間複雜度是 O(n)
• 經典的方法有三種，前序周遊、中序周遊和後序周遊。其中，前、中、後序，表示的是節點與它的左右子樹節點周遊列印的先後順序

7.2.4.1 前序周遊

• 對于樹中的任意節點來說，先列印這個節點，然後再列印它的左子樹，最後列印它的右子樹

//僞代碼實作
//遞歸
//遞推公式
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)

void preOrder(Node* root) { 
    if (root == null) {
        return; 
    }
    print root; // 此處為僞代碼，表示列印root節點 
    preOrder(root->left); 
    preOrder(root->right);
    
}
           

7.2.4.2 中序周遊

• 對于樹中的任意節點來說，先列印它的左子樹，然後再列印這個節點，最後列印它的右子樹
• 先列印根節點，然後再遞歸地列印左子樹，最後遞歸地列印右子樹

//僞代碼實作
//遞歸
//遞推公式
inOrder(r) = inOrder(r->left)->print r->inOrder(r-right)

void inOrder(Node* root) { 
    if (root == null) {
        return; 
    }
    inOrder(root->left); 
    print root; // 此處為僞代碼，表示列印root節點 
    inOrder(root->right);
    
}
           

7.2.4.3 後序周遊

• 對于樹中的任意節點來說，先列印它的左子樹，然後再列印右子樹，最後列印這個節點

//僞代碼實作
//遞歸
//遞推公式
postOrder(r) = postOrder(r->left)->postOrder(r-right)->print r

void inOrder(Node* root) { 
    if (root == null) {
        return; 
    }
    postOrder(root->left); 
    postOrder(root->right);
    print root; // 此處為僞代碼，表示列印root節點 
    
}
           

7.2.4.4 層序周遊（按層周遊）

• 借用隊列輔助即可，根節點先入隊列，然後循環從隊列中pop節點，将pop出來的節點的左子節點先入隊列，右節點後入隊列，依次循環，直到隊列為空，周遊結束

Java代碼如下：
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return new ArrayList<>(0);
        
        List<List<Integer>> result = new ArrayList<>();
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root); 
        
        Queue<TreeNode> curLevelNodes = new LinkedList<TreeNode>();
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            curLevelNodes.offer(node);
            
            if (queue.isEmpty()) {
                List<Integer> list = new ArrayList<>(curLevelNodes.size());
                while (!curLevelNodes.isEmpty()) {
                    TreeNode curNode = curLevelNodes.poll();
                    list.add(curNode.val);
                    
                    if (curNode.left != null) {
                        queue.offer(curNode.left); 
                    }
                    
                    if (curNode.right != null) {
                        queue.offer(curNode.right);
                    }
                    
                }
                result.add(list);
            }
        }
        
        
        return result;
    }
    
}
           

7.2.5 二叉查找樹 / 二叉搜尋樹 / 二叉排序樹

• 支援動态資料集合的快速插入、删除、查找操作
• 在樹中的任意一個節點，其左子樹中的每個節點的值，都要小于這個節點的值，而右子樹節點的值都大于這個節點的值
• 中序周遊二叉查找樹，可以輸出有序的資料序列，時間複雜度是 O(n)，非常高效

7.2.5.1 查找操作

• 先取根節點，如果它等于我們要查找的資料，那就傳回
• 如果要查找的資料比根節點的值小，那就在左子樹中遞歸查找
• 如果要查找的資料比根節點的值大，那就在右子樹中遞歸查找

public static class Node {
    private int data;
    private Node left;
    private Node right;
    
    public Node (int data) {
        this.data = data;
    }
}

public class BinarySearchTree {
    
    // tree 為根節點
    public Node find (Node tree,int data) {
        Node p = tree;
        while (p != null) {
            if (data < p.data) {
                p = p.left;
            } else if (data > p.data) {
                p = p.right;
            } else {
                return p;
            }
        }
        return null;
    }
}
           

7.5.2.2 插入操作

• 新插入的資料一般都是在葉子節點上，是以我們隻需要從根節點開始，依次比較要插入的資料和節點的大小關系
• 如果要插入的資料比節點的資料大，并且節點的右子樹為空，就将新資料直接插到右子節點的位置；如果不為空，就再遞歸周遊右子樹，查找插入位置。
• 同理，如果要插入的資料比節點數值小，并且節點的左子樹為空，就将新資料插入到左子節點的位置；如果不為空，就再遞歸周遊左子樹，查找插入位置

public static class Node {
    private int data;
    private Node left;
    private Node right;
    
    public Node (int data) {
        this.data = data;
    }
}

public class BinarySearchTree {

    // tree 為根節點
    public void  insert (Node tree,int data) {
        if (tree == null) {
            tree = new Node(data);
            return;
        }
        Node p = tree;
        while (p != null) {
            if (data < p.data) {
                if (p.left == null) {
                    p.left = new Node(data);
                    return;
                }
                p = p.left;
            } else if (data > p.data) {
                if (p.right == null) {
                    p.right = new Node(data);
                    return;
                }
                p = p.right;
            } 
        }
    }
}
           

7.5.2.3 删除操作

• 第一種情況： 如果要删除的節點沒有子節點，我們隻需要直接将父節點中，指向要删除節點的指針置為 null
• 第二種情況： 如果要删除的節點隻有一個子節點（隻有左子節點或者右子節點），我們隻需要更新父節點，讓它指向要删除節點的子節點就可以了
• 第三種情況： 如果要删除的節點有兩個子節點，這就比較複雜了。我們需要找到這個節點的右子樹中的最小節點，把它替換到要删除的節點上。然後再删除掉這個最小節點，因為最小節點肯定沒有左子節點（如果有左子結點，那就不是最小節點了），是以，我們可以應用上面兩條規則來删除這個最小節點

public static class Node {
    private int data;
    private Node left;
    private Node right;
    
    public Node (int data) {
        this.data = data;
    }
    
    // tree 為根節點
    public void  delete (Node tree,int data) {
        //第一步：首先找出要删除的節點
        
        //p 指向要删除的節點，初始化指向根節點
        Node p = tree;
        //記錄P的父節點，初始化為null
        Node pp = null;
        
        while (p != null && p.data != data) {
            pp = p;
            if (data > p.data) {
                p = p.right
            } else {
                p = p.left;
            }
        }
        if (p == null) {
            return; //沒有找到
        }
        
        //要删除的節點有兩個子節點
        //查找右子樹中的最小節點
        if (p.left != null && p.right != null) {
            Node minP = p.right;
            Node minPP = p; // minPP表示minP的父節點
            while (minP.left != null) {
                minPP = minP;
                minP = p.left;
            }
            // 将minP的資料替換到p中
            p.data = minP.data;
            // 下面就變成了删除minP了
            p = minP;
            pp = minPP;
        }
        
        //第二步：開始删除找到的節點
        
        //如果删除的節點是葉子節點，或者 僅有一個子節點
        Node child; //p 的子節點
        if (p.left != null) {
            child = p.left;
        } else if (p.right != null) {
            child = p.right;
        } else {
            child = null;
        }
        
        if（pp == null) {
            tree = child; //如果删除的是根節點
        } else if (pp.left == p) {
            pp.left = child;
        } else {
            pp.right = child;
        }
    } 
}

           

7.5.2.4 有了散列/哈希表，并且其動态查詢、插入、删除的時間複雜度為O(1)，相對而言二叉查找樹這些操作的時間複雜度最好才為O(logn)，那為什麼還要用二叉查找樹？

• 散清單中的資料是無序存儲的，如果要輸出有序的資料，需要先進行排序。而對于二叉查找樹來說，我們隻需要中序周遊，就可以在 O(n) 的時間複雜度内，輸出有序的資料序列
• 散清單擴容耗時很多，而且當遇到散列沖突時，性能不穩定，盡管二叉查找樹的性能不穩定，但是在工程中，我們最常用的平衡二叉查找樹的性能非常穩定，時間複雜度穩定在 O(logn)
• 籠統地來說，盡管散清單的查找等操作的時間複雜度是常量級的，但因為哈希沖突的存在，這個常量不一定比 logn 小，是以實際的查找速度可能不一定比 O(logn) 快。加上哈希函數的耗時，也不一定就比平衡二叉查找樹的效率高
• 散清單的構造比二叉查找樹要複雜，需要考慮的東西很多。比如散列函數的設計、沖突解決辦法、擴容、縮容等。平衡二叉查找樹隻需要考慮平衡性這一個問題，而且這個問題的解決方案比較成熟、固定

7.5.2.5 求一棵給定二叉樹的高度

• 思路一：遞歸，根節點高度=max(左子樹高度，右子樹高度)+1
• 思路二：采用層次周遊的方式
• 每一層記錄都記錄下目前隊列的長度，這個是隊尾，每一層隊頭從0開始。然後每周遊一個元素，隊頭下标+1。直到隊頭下标等于隊尾下标。這個時候表示目前層周遊完成。每一層剛開始周遊的時候，樹的高度+1。最後隊列為空，就能得到樹的高度

7.2.6 平衡二叉查找樹

• 二叉查找樹在頻繁的動态更新過程中，可能會出現樹的高度遠大于 log2n 的情況，進而導緻各個操作的效率下降。極端情況下，二叉樹會退化為連結清單，時間複雜度會退化到 O(n)
• 要解決這個複雜度退化的問題，我們需要設計一種平衡二叉查找樹
• 嚴格定義：二叉樹中任意一個節點的左右子樹的高度相差不能大于 1
• 但實際使用中，并不一定按嚴格定義來，隻要樹的高度不比 log2n 大很多（比如樹的高度仍然是對數量級的），我們仍然可以說，這是一個合格的平衡二叉查找樹
• 平衡二叉查找樹中“平衡”的意思，其實就是讓整棵樹左右看起來比較“對稱”、比較“平衡”，不要出現左子樹很高、右子樹很矮的情況。這樣就能讓整棵樹的高度相對來說低一些，相應的插入、删除、查找等操作的效率高一些

7.2.6.1 紅黑樹

• 近似平衡（從根到葉子節點的最長路徑不會超過最短路徑的2倍，是一種自動平衡的二叉查找樹
• 根節點是黑色的；
• 每個葉子節點都是黑色的空節點（NIL），也就是說，葉子節點不存儲資料
• 任何相鄰的節點都不能同時為紅色，也就是說，紅色節點是被黑色節點隔開的
• 每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點
• 紅黑樹的插入、删除、查找各種操作性能都比較穩定，時間複雜度都是 O(logn)
• 參考文章：清晰了解紅黑樹的演變—紅黑的含義
• 參考文章：漫畫算法：什麼是紅黑樹？

7.2.6.1.1 2-3樹

• 是二叉查找樹的變種，樹中的2和3代表兩種節點
• 2-節點即普通節點：包含一個元素，兩條子連結

• 3-節點則是擴充版，包含2個元素和三條連結：兩個元素A、B，左邊的連結指向小于A的節點，中間的連結指向介于A、B值之間的節點，右邊的連結指向大于B的節點

• 在這兩種節點的配合下，2-3樹可以保證在插入值過程中，任意葉子節點到根節點的距離都是相同的

7.2.6.1.1.1 2-3樹 插入過程

• 如果将值插入一個2-節點，則将2-節點擴充為一個3-節點
• 如果将值插入一個3-節點，分以下幾種情況
• (1).3-節點沒有父節點，即整棵樹就隻有它一個三節點。此時，将3-節點擴充為一個4-節點，即包含三個元素的節點，然後将其分解，變成一棵二叉樹，此時二叉樹依然保持平衡

• (2).3-節點有一個2-節點的父節點，此時的操作是，3-節點擴充為4-節點，然後分解4-節點，然後将分解後的新樹的父節點融入到2-節點的父節點中去

• (3).3-節點有一個3-節點的父節點，此時操作是：3-節點擴充為4-節點，然後分解4-節點，新樹父節點向上融合，上面的3-節點繼續擴充，融合，分解，新樹繼續向上融合，直到父節點為2-節點為止，如果向上到根節點都是3-節點，将根節點擴充為4-節點，然後分解為新樹，至此，整個樹增加一層，仍然保持平衡。

7.2.6.1.2 紅黑樹 與 2-3樹

• 紅黑樹的背後邏輯就是2-3樹的邏輯
• 将3-節點的兩個元素用左斜紅色的連結連接配接起來，即連接配接了兩個2-節點來表示一個3-節點
• 紅色節點标記就代表指向其的連結是紅連結，黑色标記的節點就是普通的節點
• 紅色節點是可以與其父節點合并為一個3-節點的，紅黑樹實作的其實是一個完美的黑色平衡，如果你将紅黑樹中所有的紅色連結放平，那麼它所有的葉子節點到根節點的距離都是相同的

• 紅連結放平（紅連結均為左連結）

7.2.6.2 幾種動态資料結構的對比

• 動态資料結構是支援動态的更新操作，裡面存儲的資料是時刻在變化的，通俗一點講，它不僅僅支援查詢，還支援删除、插入資料。
• 而且，這些操作都非常高效。如果不高效，也就算不上是有效的動态資料結構了

• 資料結構	優點	缺點	應用場景
  哈希表	插入删除查找都是O(1), 是最常用的	哈希沖突，不能順序周遊以及擴容縮容的性能損耗	那些不需要順序周遊，海量資料随機通路、防止重複、緩存等
  跳表	插入删除查找都是O(logn), 并且能順序周遊，區間查找非常友善（基于連結清單），支援多寫多讀	空間複雜度O(n)	不那麼在意記憶體空間的
  紅黑樹	插入删除查找都是O(logn), 中序周遊即是順序周遊，穩定	難以實作，去查找不友善	TreeMap、TreeSet、HashMap等

• 相比跳表，紅黑樹除了記憶體占用較小，其他性能并不比跳表更優。但由于曆史原因，紅黑樹使用的更廣泛

7.2.7 堆和堆排序

• 堆是一個完全二叉樹
• 堆中每一個節點的值都必須大于等于（或小于等于）其子樹中每個節點的值
• 大頂堆：每一個節點的值都大于等于左右子節點
• 小頂堆：每一個節點的值都小于等于左右子節點

7.2.7.1 如何實作一個堆 （以大頂堆為例）

• 一般用數組（i = 0，置空，不存資料）存儲堆 （因為堆是一棵完全二叉樹）
• 數組中下标為 i 的節點的左子節點，就是下标為 i∗2 的節點，右子節點就是下标為 i∗2+1 的節點，父節點就是下标為 i/2 的節點
• 如果從 0 開始存儲，節點的下标是 i，那左子節點的下标就是 2∗i+1，右子節點的下标就是 2∗i+2，父節點的下标就是 (i-1) / 2 （計算左子節點時，會多一次加法運算）

7.2.7.1.1 插入一個元素

• 堆化：順着節點所在的路徑，向上或者向下，對比，然後交換
• 讓新插入的節點與父節點對比大小。如果不滿足子節點小于等于父節點的大小關系，我們就互換兩個節點。一直重複這個過程，直到父子節點之間滿足剛說的那種大小關系
• 從下往上 堆化 比如插入 22

public class Heap {
    private int[] a; //數組，從下标1開始存儲資料
    private int capacity; //堆的容量
    private int count; //堆中已存儲的資料個數
    
    public Heap (int capacity) {
        a = new int[capacity + 1];
        this.capacity = capacity;
        count = 0;
    }
    
    public void insert (int data) {
        if (count >= capacity) { //堆滿了，無法添加資料
            return;
        }
        count++;
        a[count] = data;
        int i = count;
        
        //自下往上堆化
        while (i/2 > 0 && a[i] > a[i/2]) { // i/2 為i這個節點的父節點
            //互動節點i 與其 父節點的值
            swap(a,i,i/2);
            i = i/2;
        }
    }
    
    private void swap (int[] a,int before,int after) {
        if (a == null || before >= a.length || after >= a.length) {
            return;
        }
        int temp = a[before];
        a[before] = a[after];
        a[after] = temp;
    }
}
           

• 時間複雜度為O(logn)

7.2.7.1.2 删除堆頂元素

• 堆頂元素存儲的是堆中的最大值或者最小值
• 當我們删除堆頂元素之後，就需要把第二大的元素放到堆頂，那第二大元素肯定會出現在左右子節點中。然後我們再疊代地删除第二大節點，以此類推，直到葉子節點被删除（不過這種方法有點問題，就是最後堆化出來的堆并不滿足完全二叉樹的特性）
• 從上往下 堆化 把最後一個節點放到堆頂，然後利用同樣的父子節點對比方法。對于不滿足父子節點大小關系的，互換兩個節點，并且重複進行這個過程，直到父子節點之間滿足大小關系為止

public class Heap {
    private int[] a; //數組，從下标1開始存儲資料
    private int capacity; //堆的容量
    private int count; //堆中已存儲的資料個數
    
    public Heap (int capacity) {
        a = new int[capacity + 1];
        this.capacity = capacity;
        count = 0;
    }
    
    public void remove () {
        if (count == 0) { //堆中沒資料
            return;
        }
        
        //自上往下堆化
        a[1] = a[count];
        count--;
        int i = 1;
        while (true) {
            int maxPos = i; //預設i位置為最大元素的位置
            //如果最大元素小于目前節點的左子節點，那麼最大元素的位置為左子節點位置
            if (i * 2 <= count && a[i] < a[2*i]) {
                maxPos = i*2;
            }
            //如果最大元素小于目前節點的右子節點，那麼最大元素的位置為右子節點位置
            if (i * 2 + 1 <= count && a[maxPos] < a[2*i + 1]) {
                maxPos = i*2 + 1;
            } 
            //如果最大元素為目前節點，就跳出循環
            if (maxPos == i) {
                break;
            }
            //互動目前節點和最大節點的值
            swap(a,i,maxPos);
            
            //将目前節點指派為最大節點
            i = maxPos;
        }
    }
    
    private void swap (int[] a,int before,int after) {
        if (a == null || before >= a.length || after >= a.length) {
            return;
        }
        int temp = a[before];
        a[before] = a[after];
        a[after] = temp;
    }
}
           

• 時間複雜度為O(logn)

7.2.7.2 如何基于堆實作排序？（堆排序）

• 時間複雜度非常穩定，是 O(nlogn)
• 并且它還是原地排序算法

7.2.7.2.1 建堆

• 将數組原地建成一個堆
• 從下往上堆化，類試于插入資料
• 從上往下堆化（對下标從 n/2 開始到 1 的資料進行堆化，下标是 n/2 +1 到 n 的節點是葉子節點，不需要堆化)

private static void buildHeap(int[] a, int n) {
  for (int i = n/2; i >= 1; --i) {
    heapify(a, n, i);
  }
}

private static void heapify(int[] a, int n, int i) {
  while (true) {
    int maxPos = i;
    if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
    if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
    if (maxPos == i) break;
    swap(a, i, maxPos);
    i = maxPos;
  }
}
           

• 時間複雜度為O(n)

7.2.7.2.2 排序

• 建堆結束之後，數組中的資料已經是按照大頂堆的特性來組織的。
• 數組中的第一個元素就是堆頂，也就是最大的元素。我們把它跟最後一個元素交換，那最大元素就放到了下标為 n 的位置
• 然後再通過堆化的方法，将剩下的 n−1 個元素重新建構成堆。堆化完成之後，我們再取堆頂的元素，放到下标是 n−1 的位置，一直重複這個過程，直到最後堆中隻剩下标為 1 的一個元素，排序工作就完成了

// n表示資料的個數，數組a中的資料從下标1到n的位置。
public static void sort(int[] a, int n) {
  buildHeap(a, n); //堆化 見上面代碼
  int k = n;
  while (k > 1) {
    swap(a, 1, k);
    --k;
    heapify(a, k, 1); //從上往下堆化
  }
}
           

• 排序複雜度 O(nlogn)

7.2.7.3 在實際開發中，為什麼快速排序要比堆排序性能好？

7.2.7.3.1 堆排序資料通路的方式沒有快速排序友好

• 快速排序來說，資料是順序通路的,而對于堆排序來說，資料是跳着通路的,這樣對CPU緩存不友好

7.2.7.3.2 對于同樣的資料，在排序過程中，堆排序算法的資料交換次數要多于快速排序

• 因為每次堆化，反而會使資料更無序，增加了逆序度

7.2.7.4 堆的應用場景

7.2.7.4.1 利用堆求 Top K

• 1.如何在一個包含 n 個資料的數組中，查找前 K 大資料呢？
• 可以維護一個大小為 K的小頂堆，順序周遊數組，從數組中取出資料與堆頂元素比較。
• 如果比堆頂元素大，我們就把堆頂元素删除，并且将這個元素插入到堆中；
• 如果比堆頂元素小，則不做處理，繼續周遊數組。
• 這樣等數組中的資料都周遊完之後，堆中的資料就是前 K 大資料了
• 周遊數組需要 O(n) 的時間複雜度，一次堆化操作需要 O(logK) 的時間複雜度，是以最壞情況下，n 個元素都入堆一次，時間複雜度就是 O(nlogK)
• 2.求實時topK？
• 可以一直都維護一個 K大小的小頂堆，當有資料被添加到集合中時，我們就拿它與堆頂的元素對比。
• 如果比堆頂元素大，我們就把堆頂元素删除，并且将這個元素插入到堆中；
• 如果比堆頂元素小，則不做處理。
• 這樣，無論任何時候需要查詢目前的前 K 大資料，我們都可以立刻傳回
• 3.一個包含 10 億個搜尋關鍵詞的日志檔案，如何快速擷取到 Top 10 最熱門的搜尋關鍵詞呢？（單機，可使用記憶體為1G）
• 思路：就是利用哈希表統計出相同關鍵詞出現的頻率，然後利用堆，求Top 10；
• 建立 10 個空檔案 00，01，02，……，09。我們周遊這10億個關鍵詞，并且通過某個雜湊演算法對其求哈希值，然後哈希值同10取模，得到的結果就是這個搜尋關鍵詞應該被分到的檔案編号
• 對這 10 億個關鍵詞分片之後，每個檔案都隻有1億的關鍵詞，去除掉重複的，可能就隻有 1000 萬個，每個關鍵詞平均 50 個位元組，是以總的大小就是 500MB。1GB 的記憶體完全可以放得下
• 我們針對每個包含 1 億條搜尋關鍵詞的檔案，利用散清單和堆，分别求出 Top 10，然後把這個 10 個 Top 10 放在一塊，然後取這 100 個關鍵詞中，出現次數最多的 10 個關鍵詞，這就是這 10 億資料中的 Top 10 最頻繁的搜尋關鍵詞了

7.2.7.4.2 優先隊列

• 1.根據不同優先級來處理網絡請求
• 2.合并有序小檔案
• 假設我們有 100 個小檔案，每個檔案的大小是 100MB，每個檔案中存儲的都是有序的字元串。我們希望将這些 100 個小檔案合并成一個有序的大檔案
• 利用數組： 從這 100 個檔案中，各取第一個字元串，放入數組中，然後比較大小，把最小的那個字元串放入合并後的大檔案中，并從數組中删除，依次類推，直到所有的檔案中的資料都放入到大檔案為止。（每次都要循環數組，時間複雜度為O(n) 不是很高效）
• 利用堆： 将從小檔案中取出來的字元串放入到小頂堆中，那堆頂的元素，也就是優先級隊列隊首的元素，就是最小的字元串
• 将這個字元串放入到大檔案中，并将其從堆中删除。然後再從小檔案中取出下一個字元串，放入到堆中。循環這個過程，就可以将 100 個小檔案中的資料依次放入到大檔案中。（堆的插入和删除時間複雜度都為O(logn)，更加高效）
• 3.高性能定時器

7.2.7.4.3 求動态資料集合中的中位數

• 需要維護兩個堆，一個大頂堆，一個小頂堆。
• 大頂堆中存儲前半部分資料，小頂堆中存儲後半部分資料，且小頂堆中的資料都大于大頂堆中的資料
• n 是偶數，那前 n/2 個資料存儲在大頂堆中，後 n/2 個資料存儲在小頂堆中
• n 是奇數，情況是類似的,那前 n/2 + 1 個資料存儲在大頂堆中，後 n/2 個資料存儲在小頂堆中
• 新進元素值大于等于小頂堆堆頂元素的，插入小頂堆，否則插入大頂堆。
• 但由于動态添加，有可能不滿足這個關系，可以從一個堆中不停地将堆頂元素移動到另一個堆，通過這樣的調整，來讓兩個堆中的資料滿足上面的約定
• 這樣，大頂堆中的堆頂元素就是我們要找的中位數

8. 圖

• 圖中的元素我們就叫作頂點（vertex）。
• 圖中的一個頂點可以與任意其他頂點建立連接配接關系。我們把這種建立的關系叫作邊（edge）
• 度：表示一個頂點有多少條邊
• 邊沒有有方向的圖叫作 “無向圖”

• 邊有方向的圖叫作 “有向圖”

• 每條邊都有一個權重叫做 "帶權圖"

8.1 圖的存儲

8.1.1 鄰接矩陣

• 鄰接矩陣的底層依賴一個二維數組
• 對于無向圖來說，如果頂點 i 與頂點 j 之間有邊，我們就将 A[i][j]和 A[j][i]标記為 1；
• 對于有向圖來說，如果頂點 i 到頂點 j 之間，有一條箭頭從頂點 i 指向頂點 j 的邊，那我們就将 A[i][j]标記為 1；同理，如果有一條箭頭從頂點 j 指向頂點 i 的邊，我們就将 A[j][i]标記為 1
• 帶權圖，數組中就存儲相應的權重

• 優點：簡單、直覺、基于數組和矩陣，友善計算，時間上相對高效
• 缺點：比較浪費存儲空間

8.1.1 鄰接表

• 每個頂點對應一條連結清單，連結清單中存儲的是與這個頂點相連接配接的其他頂點

• 優點：比較節省空間
• 缺點：計算和使用 不是很高效

8.1.1.1 代碼實作

public class Graph { // 無向圖
  private int v; // 頂點的個數
  private LinkedList<Integer> adj[]; // 鄰接表

  public Graph(int v) {
    this.v = v;
    adj = new LinkedList[v];
    for (int i=0; i<v; ++i) {
      adj[i] = new LinkedList<>();
    }
  }

  public void addEdge(int s, int t) { // 無向圖一條邊存兩次
    adj[s].add(t);
    adj[t].add(s);
  }
}
           

8.2 搜尋算法

• 基本是基于“圖”
• 圖上的搜尋算法，最直接的了解就是，在圖中找出從一個頂點出發，到另一個頂點的路徑

8.2.1 廣度優先搜尋(BFS)

• 它其實就是一種 “地毯式”層層推進的搜尋政策，即先查找離起始頂點最近的，然後是次近的，依次往外搜尋

• 時間複雜度：O(E) E為邊的條數
• 空間複雜度：O(V) V為頂點的個數
• 僅适用于狀态空間不大，也就是說圖不大的搜尋

8.2.2 深度優先搜尋(DFS)

• 類似 “走迷宮”
• 假設你站在迷宮的某個岔路口，然後想找到出口。你随意選擇一個岔路口來走，走着走着發現走不通的時候，你就回退到上一個岔路口，重新選擇一條路繼續走，直到最終找到出口。這種走法就是一種深度優先搜尋政策

• 時間複雜度：O(E) E為邊的條數
• 空間複雜度：O(V) V為頂點的個數
• 僅适用于狀态空間不大，也就是說圖不大的搜尋
• 用的是回溯思想，非常适合用遞歸實作

9. 字元串比對

• 主串：目前的字元串本身
• 模式串：被查找/比對的字元串
• 在字元串 A 中查找字元串 B，那字元串 A 就是主串，字元串 B 就是模式串
• 主串的長度為n，模式串的長度為m

9.1 BF算法

• 暴力比對算法，也叫樸素比對算法
• 我們在主串中，檢查起始位置分别是 0、1、2…n-m 且長度為 m 的 n-m+1 個子串，看有沒有跟模式串比對的
• 時間複雜度：O(n*m)

9.1.1 為什麼BF 算法的時間複雜度很高，是 O(n*m)，但在實際的開發中，但它卻是一個比較常用的字元串比對算法？

• 實際的軟體開發中，大部分情況下，模式串和主串的長度都不會太長。而且每次模式串與主串中的子串比對的時候，當中途遇到不能比對的字元的時候，就可以就停止了，不需要把 m 個字元都比對一下。大部分情況下，算法執行效率要比O(n*m)高很多
• BF算法思想簡單，代碼實作也非常簡單。簡單意味着不容易出錯，如果有 bug 也容易暴露和修複。在工程中，在滿足性能要求的前提下，簡單是首選

9.2 RK算法

• 全稱叫 Rabin-Karp 算法，是由它的兩位發明者 Rabin 和 Karp 的名字來命名的
• 其實就是 BF 算法的更新版
• 算法思路：通過雜湊演算法對主串中的 n-m+1 個子串分别求哈希值，然後逐個與模式串的哈希值比較大小。如果某個子串的哈希值與模式串相等，那就說明對應的子串和模式串比對了（當有哈希沖突時，再對比一下子串和模式串本身就好了）。因為哈希值是一個數字，數字之間比較是否相等是非常快速的，是以模式串和子串比較的效率就提高了

9.3 BM算法

• 一種非常高效的字元串比對算法
• 核心思想：當遇到不比對的字元時，BF 算法和 RK 算法的做法是，模式串往後滑動一位；BM 算法 能夠跳過一些肯定不會比對的情況，将模式串往後多滑動幾位

9.3.1 壞字元規則

• 從模式串的末尾往前倒着比對，當我們發現某個字元沒法比對的時候。我們把這個沒有比對的字元叫作壞字元（主串中字元）
• 當發生不比對的時候，我們把壞字元對應的模式串中的字元下标記作 si。
• 如果壞字元在模式串中存在，我們把這個壞字元在模式串中的下标記作 xi。如果不存在，我們把 xi 記作 -1。那模式串往後移動的位數就等于 si-xi。（注意，這裡說的下标，都是字元在模式串的下标）

• BM 算法在最好情況下的時間複雜度非常低，是 O(n/m)
• 不過，單純使用壞字元規則還是不夠的。因為根據 si-xi 計算出來的移動位數，有可能是負數，比如主串是 aaaaaaaaaaaaaaaa，模式串是 baaa

9.3.2 好字尾規則

• 把已經比對的 bc 叫作好字尾，記作{u}。我們拿它在模式串中查找，如果找到了另一個跟{u}相比對的子串{u*}，那我們就将模式串滑動到子串{u*}與主串中{u}對齊的位置

• 當模式串中不存在等于{u}的子串時,不僅要看好字尾在模式串中，是否有另一個比對的子串，我們還要考察好字尾的字尾子串，是否存在跟模式串的字首子串比對的
• 所謂某個字元串 s 的字尾子串，就是最後一個字元跟 s 對齊的子串，比如 abc 的字尾子串就包括 c, bc。所謂字首子串，就是起始字元跟 s 對齊的子串，比如 abc 的字首子串有 a，ab
• 從好字尾的字尾子串中，找一個最長的并且能跟模式串的字首子串比對的，假設是{v}，然後将模式串滑動到如圖所示的位置

10 算法思想

10.1 貪心算法

• 不要刻意去記憶貪心算法的原理，多練習才是最有效的學習方法
• 貪心算法的本質就是"在滿足限制條件下，隻考慮目前最優的步驟，而不顧全大局"
• 基本上可以用貪心算法解決的問題：針對一組資料，我們定義了限制值和期望值，希望從中選出幾個資料，在滿足限制值的情況下，期望值最大
• 貪心算法得到的結果不一定是最優解

10.1.1 具體應用場景

10.1.1.1 分糖果

• 我們有 m 個糖果和 n 個孩子。我們現在要把糖果分給這些孩子吃，但是糖果少，孩子多（m<n），是以糖果隻能配置設定給一部分孩子。每個糖果的大小不等，這 m 個糖果的大小分别是 s1，s2，s3，……，sm。除此之外，每個孩子對糖果大小的需求也是不一樣的，隻有糖果的大小大于等于孩子的對糖果大小的需求的時候，孩子才得到滿足。假設這 n 個孩子對糖果大小的需求分别是 g1，g2，g3，……，gn
• 問題是，如何配置設定糖果，能盡可能滿足最多數量的孩子，一個孩子隻能分一個糖果？
• 貪心算法思想：對于一個孩子來說，如果小的糖果可以滿足，我們就沒必要用更大的糖果，這樣更大的就可以留給其他對糖果大小需求更大的孩子。另一方面，對糖果大小需求小的孩子更容易被滿足，是以，我們可以從需求小的孩子開始配置設定糖果。因為滿足一個需求大的孩子跟滿足一個需求小的孩子，對我們期望值的貢獻是一樣的。我們每次從剩下的孩子中，找出對糖果大小需求最小的，然後發給他剩下的糖果中能滿足他的最小的糖果，這樣得到的配置設定方案，也就是滿足的孩子個數最多的方案

10.1.1.2 錢币找零

• 假設我們有 1 元、2 元、5 元、10 元、20 元、50 元、100 元這些面額的紙币，它們的張數分别是 c1、c2、c5、c10、c20、c50、c100。我們現在要用這些錢來支付 K 元，最少要用多少張紙币呢？
• 貪心算法思想：在貢獻相同期望值（紙币數目）的情況下，我們希望多貢獻點金額，這樣就可以讓紙币數更少。先用面值最大的來支付，如果不夠，就繼續用更小一點面值的，以此類推，最後剩下的用 1 元來補齊

10.1.1.3 區間覆寫

• 具體參考：用貪心算法解決區間覆寫問題

10.1.2 相關案例

10.1.2.1 在一個非負整數 a 中，我們希望從中移除 k 個數字，讓剩下的數字值最小，如何選擇移除哪 k 個數字呢？

• 由最高位開始，比較低一位數字，如高位大，移除，若高位小，則向右移一位繼續比較兩個數字，直到高位大于低位則移除，循環k次
• 比如 4556847594546 移除5位
• 第一次 455647594546 -> 45547594546 -> 4547594546 -> 447594546 -> 44594546

10.1.2.2 假設有 n 個人等待被服務，但是服務視窗隻有一個，每個人需要被服務的時間長度是不同的，如何安排被服務的先後順序，才能讓這 n 個人總的等待時間最短？

• 想讓所有人的等待時間最短，那麼我們得先處理服務時間短的，盡快把他們處理完了才能夠處理後面的人！

10.2 分治算法

• 典型應用: MapReduce
• 核心思想：分而治之，也就是将原問題劃分成 n 個規模較小，并且結構與原問題相似的子問題，遞歸地解決這些子問題，然後再合并其結果，就得到原問題的解
• 分治算法是一種處理問題的思想，遞歸是一種程式設計技巧

10.2.1 能用分治算法解決問題的特征

• 原問題與分解成的小問題具有相同的模式
• 原問題分解成的子問題可以獨立求解，子問題之間沒有相關性，這一點是分治算法跟動态規劃的明顯差別
• 具有分解終止條件，也就是說，當問題足夠小時，可以直接求解
• 可以将子問題合并成原問題，而這個合并操作的複雜度不能太高，否則就起不到減小算法總體複雜度的效果了

10.3 回溯算法

• 回溯的處理思想，有點類似枚舉搜尋。我們枚舉所有的解，找到滿足期望的解
• 都是用來解決廣義的搜尋問題，也就是，從一組可能的解中，選擇出一個滿足要求的解
• 回溯算法本質上就是枚舉，優點在于其類似于摸着石頭過河的查找政策，且可以通過剪枝少走冤枉路。
• 它可能适合應用于缺乏規律，或我們還不了解其規律的搜尋場景中
• 回溯算法的複雜度比較高，是指數級别的

10.3.1 八皇後問題

• 有一個 8x8 的棋盤，希望往裡放 8 個棋子（皇後），每個棋子所在的行、列、對角線都不能有另一個棋子

public class EightQueens {

    //全局或成員變量,下标表示行,值表示queen存儲的列
    int[] result = new int[8];
    
    public void cal8Queens (int row) {
        if (row == 8) {// 8個棋子都放置好了，列印結果
            printQueens(result);
            return; // 8行棋子都放好了，已經沒法再往下遞歸了，是以就return
        }
        for (int column = 0;column < 8;column++) {
            if (isOk(row,column)) {//如果已經放好
                result[row] = column;// 第row行的棋子放到了column列
                cal8Queens(row+1); // 遞歸考察下一行
            }
        }
    }
    
    //判斷 row 行 column 列放置是否合适
    private boolean isOk (int row,int column) {
        int leftup = column - 1;  //左上角對角線
        int rightup = column + 1; //右上角對角線
        
        for (int i = row -1;i >= 0;i--) { //逐行往上考察每一行
            if (result[i] == column) {// 第i行的column列有棋子嗎？
                return false;
            }
            if (leftup >= 0) { // 考察左上對角線： 
                if (result[i] == leftup) { //第i行leftup列有棋子嗎？
                    return false; 
                }   
            }
            if (rightup < 8) { // 考察右上對角線
                if (result[i] == rightup) { // 第i行rightup列有棋子嗎？
                   return false;  
                }
            } 
            leftup--; 
            rightup++;
        }
        return true; 
    }
    

    private void printQueens(int[] result) { // 列印出一個二維矩陣
        for (int row = 0; row < 8; ++row) {
            for (int column = 0; column < 8; ++column) {
                if (result[row] == column) System.out.print("Q ");
                else System.out.print("* ");
            }
            System.out.println();
        }
        System.out.println();
    }
}
           

10.3.2 0-1背包問題

• 有一個背包，背包總的承載重量是 Wkg。現在我們有 n 個物品，每個物品的重量不等，并且不可分割。我們現在期望選擇幾件物品，裝載到背包中。在不超過背包所能裝載重量的前提下，如何讓背包中物品的總重量最大？

public class BagQuestion {
    
    //存儲背包中物品總重量的最大值
    public int maxW = Integer.MiN_VALUE;
    
    // countWeight表示目前已經裝進去的物品的重量和；i表示考察到哪個物品了；
    // bagWeight表示背包最大乘重；items表示物品的重量數組；n表示物品個數
    // 假設背包可承受重量100，物品個數10，物品重量存儲在數組a中，那可以這樣調用函數：
    // bugFunction(0, 0, a, 10, 100)
    public void bugFunction (int i,int countWeight,int[] items,int n,int bagWeight) {
        //如果裝滿了 或者 已經考察完所有物品，則結束
        if (countWeight == bagWeight || i == n) {
            if (countWeight > maxW) {
                maxW = countWeight;
            }
            return;
        }
        //下個物品不放進背包，即不考查
        bugFunction(i+1,countWeight,items,n,bagWeight);
        
        //将下個物品放進背包
        // 已經裝好的物品總量不能超過背包的承受重量
        if (countWeight + item[i] <= bagWeight) {
            bugFunction(i+1,countWeight + item[i],items,n,bagWeight);
        }
    }
}
           

10.4 動态規劃

• 把問題分解為多個階段，每個階段對應一個決策。
• 記錄每一個階段可達的狀态集合（去掉重複的），然後通過目前階段的狀态集合，來推導下一個階段的狀态集合，動态地往前推進
• 比較适合用來求解最優問題，比如求最大值、最小值等等

10.4.1 什麼樣的問題适合用動态規劃來解決

• "一個模型三個特征"

10.4.1.1 多階段決策最優解模型

• 一般是用動态規劃來解決最優問題
• 解決問題的過程，需要經曆多個決策階段
• 每個決策階段都對應着一組狀态
• 然後我們尋找一組決策序列，經過這組決策序列，能夠産生最終期望求解的最優值

10.4.1.2 最優子結構

• 最優子結構指的是，問題的最優解包含子問題的最優解
• 可以通過子問題的最優解，推導出問題的最優解
• 也可以了解為，後面階段的狀态可以通過前面階段的狀态推導出來

10.4.1.3 無後效性

• 第一層含義是，在推導後面階段的狀态的時候，我們隻關心前面階段的狀态值，不關心這個狀态是怎麼一步一步推導出來的
• 第二層含義是，某階段狀态一旦确定，就不受之後階段的決策影響
• 隻要滿足前面提到的動态規劃問題模型，其實基本上都會滿足無後效性

10.4.1.4 重複子問題

• 不同的決策序列，到達某個相同的階段時，可能會産生重複的狀态

10.4.2 動态規劃解題思路

10.4.2.1 狀态轉移表法

• 一般能用動态規劃解決的問題，都可以使用回溯算法的暴力搜尋解決
• 是以，當我們拿到問題的時候，我們可以先用簡單的回溯算法解決，然後定義狀态，每個狀态表示一個節點，然後對應畫出遞歸樹。
• 從遞歸樹中，我們很容易可以看出來，是否存在重複子問題，以及重複子問題是如何産生的。
• 以此來尋找規律，看是否能用動态規劃解決
• 先畫出一個狀态表。狀态表一般都是二維的，是以你可以把它想象成二維數組。
• 其中，每個狀态包含三個變量，行、列、數組值。
• 我們根據決策的先後過程，從前往後，根據遞推關系，分階段填充狀态表中的每個狀态。最後，我們将這個遞推填表的過程，翻譯成代碼，就是動态規劃代碼了
• 如果是高維的，就不适合用狀态轉移表法來解決了
• 回溯算法實作 - 定義狀态 - 畫遞歸樹 - 找重複子問題 - 畫狀态轉移表 - 根據遞推關系填表 - 将填表過程翻譯成代碼

10.4.2.2 狀态轉移方程法

• 類似遞歸的解題思路
• 根據最優子結構，寫出遞歸公式，也就是所謂的狀态轉移方程，是解決動态規劃的關鍵
• 找最優子結構 - 寫狀态轉移方程 - 将狀态轉移方程翻譯成代碼

10.4.3 四種算法的比較分析

• 貪心、回溯、動态規劃可以歸為一類，都可以抽象成多階段決策最優解模型；分治算法單獨可以作為一類
• 回溯算法是個“萬金油”（窮舉搜尋）。基本上能用的動态規劃、貪心解決的問題，我們都可以用回溯算法解決，不過，回溯算法的時間複雜度非常高，是指數級别的，隻能用來解決小規模資料的問題
• 能用動态規劃解決的問題，需要滿足三個特征，最優子結構、無後效性和重複子問題；而分治算法要求分割成的子問題，不能有重複子問題
• 貪心算法實際上是動态規劃算法的一種特殊情況。它能解決的問題需要滿足三個條件，最優子結構、無後效性和貪心選擇性（這裡我們不怎麼強調重複子問題）
• “貪心選擇性”的意思是，通過局部最優的選擇，能産生全局的最優選擇。每一個階段，我們都選擇目前看起來最優的決策，所有階段的決策完成之後，最終由這些局部最優解構成全局最優解。