目錄
第1章 算法之美 1
1.1　生活中的算法——猜數游戲 1
1.1.1 好玩的猜數游戲 2
1.1.2 游戲的秘密——二分搜索技術 2
1.1.3 猜數游戲算法實現 4
1.2　算法的指標——空間復雜度和時間復雜度 6
1.2.1 時間復雜度 6
1.2.2 空間復雜度 9
1.3　經典算法回顧——排序算法 10
1.3.1 冒泡排序 10
1.3.2 簡單選擇排序 14
1.3.3 直接插入排序 19
1.4　怎樣才能學好算法 23
第2章 貪心算法 24
2.1　短淺的眼光——貪心 24
2.1.1 適當的貪心——壞事變好事 25
2.1.2 過度貪心——賠了夫人又折兵 25
2.1.3 為貪心加上限制 25
2.2　美麗心靈——哈夫曼編碼 26
2.2.1 認識哈夫曼編碼 26
2.2.2 如何設計哈夫曼編碼 27
2.2.3 哈夫曼編碼算法實現 33
2.3　帶你去旅行——單源最短路徑 36
2.3.1 如何最快到朋友家做客 36
2.3.2 從最短的第一條路開始分析 37
2.3.3 找到抵達朋友家的最短路徑 38
2.3.4 Dijkstra算法實現 44
2.4　選擇困難癥——背包問題 46
2.4.1 如何裝沙子賺更多的錢 47
2.4.2 海盜的智慧 47
2.4.3 背包問題算法實現 50
2.5　搬家?guī)煾档臒�惱——集裝箱裝載問題 52
2.5.1 如何裝更多的物品 53
2.5.2 搬家?guī)煾档氖�年經�?53
2.5.3 裝載問題算法實現 55
第3章 分而治之算法 58
3.1　縱橫捭闔，各個擊破——分而治之 58
3.1.1 分而治之——把復雜的事情簡單化 59
3.1.2 可分可治，缺一不可 59
3.1.3 合久必分，分久必合——治而合之 60
3.2　真幣和假幣——偽幣問題 61
3.2.1 可惡的假幣 62
3.2.2 先對一半的硬幣進行考慮 62
3.2.3 找出硬幣的規(guī)律 64
3.3　再談排序算法（1）——合并排序 66
3.3.1 如何將分而治之思想應用到合并排序上 67
3.3.2 先對一半的數字進行考慮 67
3.3.3 合并排序算法實現 70
3.4　再談排序算法（2）——快速排序 74
3.4.1 如何將分而治之思想應用到快速排序上 74
3.4.2 找到一個“分”的中心 75
3.4.3 快速排序算法實現 79
3.4.4 排序算法總結 81
3.5　累人的比賽——循環(huán)賽日程安排 82
3.5.1 最公平的比賽 82
3.5.2 如何設計循環(huán)賽 83
3.5.3 找出循環(huán)賽的排列規(guī)律 86
第4章 樹算法 89
4.1　生活中的“樹” 89
4.1.1 炎黃子孫，生生不息 90
4.1.2 學校的組織結構 90
4.1.3 操作系統(tǒng)的目錄結構 91
4.2　一葉一菩提——二叉樹的遍歷 92
4.2.1 什么是二叉樹 92
4.2.2 二叉樹的前序遍歷 92
4.2.3 二叉樹的中序遍歷 97
4.2.4 二叉樹的后序遍歷 102
4.2.5 二叉樹的平層遍歷 107
4.3　重建家譜圖——二叉樹的還原 111
4.3.1 什么是二叉樹的還原 112
4.3.2 前序遍歷和中序遍歷還原家譜圖 113
4.3.3 中序遍歷和后序遍歷還原家譜圖 118
4.4　十年樹木，百年樹人——二叉樹的高度 123
4.4.1 什么是樹的高度 123
4.4.2 在樹的遍歷基礎上增加高度信息 124
4.4.3 遍歷樹獲得高度信息 126
4.5　尋根溯源——找到所有祖先結點 128
4.5.1 什么是樹的祖先 128
4.5.2 在樹的遍歷基礎上增加結點找到信息 129
4.5.3 遍歷樹獲得所有祖先 131
第5章 圖算法 134
5.1　生活中的“圖” 134
5.1.1 城市的交通軌道 135
5.1.2 人與人之間的關系 136
5.1.3 互聯網的連接 136
5.2　尋找所有的城市——有向圖的遍歷 137
5.2.1 什么是有向圖 137
5.2.2 有向圖的深度優(yōu)先遍歷 138
5.2.3 有向圖的廣度優(yōu)先遍歷 144
5.3　最短的管道——Kruskal算法 149
5.3.1 如何鋪設最短的管道 149
5.3.2 什么是最小生成樹 150
5.3.3 Kruskal算法的貪心思想 151
5.3.4 Kruskal算法實現 156
5.4　再談最短的管道——Prim算法 158
5.4.1 基于管道的邊和結點貪心的區(qū)別 159
5.4.2 Prim算法的貪心思想 159
5.4.3 Prim算法實現 162
5.5　多源最短路徑——Floyd算法 164
5.5.1 朋友之間相互訪問的最短路徑 164
5.5.2 自上而下分析朋友之間的最短路徑 165
5.5.3 自下而上迭代朋友之間的最短路徑 166
5.5.4 Floyd算法實現 172
第6章 動態(tài)規(guī)劃算法 176
6.1　長遠的眼光——動態(tài)規(guī)劃 176
6.1.1 時間倒流，改變歷史 177
6.1.2 慎用貪心算法 177
6.1.3 強者恒強，弱者恒弱——最優(yōu)子結構 178
6.2　智能的語言翻譯——編輯距離 178
6.2.1 設計語言翻譯系統(tǒng) 179
6.2.2 考慮最后一次編輯情況 180
6.2.3 自下而上進行距離編輯 186
6.3　智能的電梯——電梯優(yōu)化 196
6.3.1 設計智能電梯 196
6.3.2 先考慮最后一次電梯停留的情況 197
6.3.3 自下而上計算電梯的停留過程 200
6.4　名字的相似度——最長公共子序列 208
6.4.1 外國人名的相似度 208
6.4.2 考慮最后一個字符比較情況 209
6.4.3 自下而上進行距離編輯 213
第7章 回溯法 219
7.1　現代計算機的福音——回溯法 220
7.1.1 讓猴子打出《莎士比亞全集》 220
7.1.2 一條路走到黑——深度遍歷 221
7.1.3 亂花漸欲迷人眼——搜索中的剪枝 223
7.2　不能攻擊的皇后——8個皇后問題 224
7.2.1 一山不容二虎 224
7.2.2 如何設計8個皇后的解向量 226
7.2.3 搜索過程中的剪枝 228
7.3　絕望的小老鼠——迷宮中的小老鼠 241
7.3.1 上帝視角幫助小老鼠 241
7.3.2 小老鼠如何進行搜索 242
7.3.3 小老鼠的出逃之路 248
7.4　再談0/1背包問題 253
7.4.1 背包問題回顧 253
7.4.2 還可以使用貪心算法求解嗎 253
7.4.3 通過搜索求解背包問題 255
7.5　再談集裝箱裝載問題 262
7.5.1 集裝箱裝載問題回顧 263
7.5.2 使用貪心算法求解而存在的問題 263
7.5.3 通過搜索求解裝載問題 264
第8章 分支限界法 276
8.1　一步一個腳印——分支限界 277
8.1.1 步步為營——廣度遍歷 277
8.1.2 剪掉沒有營養(yǎng)的分支 279
8.1.3 條條大路通羅馬——和回溯法的區(qū)別 280
8.2　再談迷宮中的小老鼠問題 281
8.2.1 迷宮中的小老鼠問題回顧 281
8.2.2 使用分支限界思路規(guī)劃小老鼠的路徑 283
8.2.3 小老鼠的出逃之路 287
8.3　三談0/1背包問題 291
8.3.1 0/1背包問題回顧 292
8.3.2 使用分支限界的思路裝船 294
8.3.3 背包的搜索過程 300
8.4　三談集裝箱裝載問題 305
8.4.1 集裝箱裝載問題回顧 305
8.4.2 使用分支限界的思路裝載集裝箱 307
8.4.3 集裝箱的裝載過程 314