目錄
第1章 算法之美 1
1.1　生活中的算法——猜數(shù)游戲 1
1.1.1 好玩的猜數(shù)游戲 2
1.1.2 游戲的秘密——二分搜索技術(shù) 2
1.1.3 猜數(shù)游戲算法實(shí)現(xiàn) 4
1.2　算法的指標(biāo)——空間復(fù)雜度和時(shí)間復(fù)雜度 6
1.2.1 時(shí)間復(fù)雜度 6
1.2.2 空間復(fù)雜度 9
1.3　經(jīng)典算法回顧——排序算法 10
1.3.1 冒泡排序 10
1.3.2 簡單選擇排序 14
1.3.3 直接插入排序 19
1.4　怎樣才能學(xué)好算法 23
第2章 貪心算法 24
2.1　短淺的眼光——貪心 24
2.1.1 適當(dāng)?shù)呢澬摹�—壞事變好�?25
2.1.2 過度貪心——賠了夫人又折兵 25
2.1.3 為貪心加上限制 25
2.2　美麗心靈——哈夫曼編碼 26
2.2.1 認(rèn)識哈夫曼編碼 26
2.2.2 如何設(shè)計(jì)哈夫曼編碼 27
2.2.3 哈夫曼編碼算法實(shí)現(xiàn) 33
2.3　帶你去旅行——單源最短路徑 36
2.3.1 如何最快到朋友家做客 36
2.3.2 從最短的第一條路開始分析 37
2.3.3 找到抵達(dá)朋友家的最短路徑 38
2.3.4 Dijkstra算法實(shí)現(xiàn) 44
2.4　選擇困難癥——背包問題 46
2.4.1 如何裝沙子賺更多的錢 47
2.4.2 海盜的智慧 47
2.4.3 背包問題算法實(shí)現(xiàn) 50
2.5　搬家?guī)煾档臒�惱——集裝箱裝載問題 52
2.5.1 如何裝更多的物品 53
2.5.2 搬家?guī)煾档氖�年�?jīng)驗(yàn) 53
2.5.3 裝載問題算法實(shí)現(xiàn) 55
第3章 分而治之算法 58
3.1　縱橫捭闔，各個(gè)擊破——分而治之 58
3.1.1 分而治之——把復(fù)雜的事情簡單化 59
3.1.2 可分可治，缺一不可 59
3.1.3 合久必分，分久必合——治而合之 60
3.2　真幣和假幣——偽幣問題 61
3.2.1 可惡的假幣 62
3.2.2 先對一半的硬幣進(jìn)行考慮 62
3.2.3 找出硬幣的規(guī)律 64
3.3　再談排序算法（1）——合并排序 66
3.3.1 如何將分而治之思想應(yīng)用到合并排序上 67
3.3.2 先對一半的數(shù)字進(jìn)行考慮 67
3.3.3 合并排序算法實(shí)現(xiàn) 70
3.4　再談排序算法（2）——快速排序 74
3.4.1 如何將分而治之思想應(yīng)用到快速排序上 74
3.4.2 找到一個(gè)“分”的中心 75
3.4.3 快速排序算法實(shí)現(xiàn) 79
3.4.4 排序算法總結(jié) 81
3.5　累人的比賽——循環(huán)賽日程安排 82
3.5.1 最公平的比賽 82
3.5.2 如何設(shè)計(jì)循環(huán)賽 83
3.5.3 找出循環(huán)賽的排列規(guī)律 86
第4章 樹算法 89
4.1　生活中的“樹” 89
4.1.1 炎黃子孫，生生不息 90
4.1.2 學(xué)校的組織結(jié)構(gòu) 90
4.1.3 操作系統(tǒng)的目錄結(jié)構(gòu) 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 在樹的遍歷基礎(chǔ)上增加高度信息 124
4.4.3 遍歷樹獲得高度信息 126
4.5　尋根溯源——找到所有祖先結(jié)點(diǎn) 128
4.5.1 什么是樹的祖先 128
4.5.2 在樹的遍歷基礎(chǔ)上增加結(jié)點(diǎn)找到信息 129
4.5.3 遍歷樹獲得所有祖先 131
第5章 圖算法 134
5.1　生活中的“圖” 134
5.1.1 城市的交通軌道 135
5.1.2 人與人之間的關(guān)系 136
5.1.3 互聯(lián)網(wǎng)的連接 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 如何鋪設(shè)最短的管道 149
5.3.2 什么是最小生成樹 150
5.3.3 Kruskal算法的貪心思想 151
5.3.4 Kruskal算法實(shí)現(xiàn) 156
5.4　再談最短的管道——Prim算法 158
5.4.1 基于管道的邊和結(jié)點(diǎn)貪心的區(qū)別 159
5.4.2 Prim算法的貪心思想 159
5.4.3 Prim算法實(shí)現(xiàn) 162
5.5　多源最短路徑——Floyd算法 164
5.5.1 朋友之間相互訪問的最短路徑 164
5.5.2 自上而下分析朋友之間的最短路徑 165
5.5.3 自下而上迭代朋友之間的最短路徑 166
5.5.4 Floyd算法實(shí)現(xiàn) 172
第6章 動態(tài)規(guī)劃算法 176
6.1　長遠(yuǎn)的眼光——動態(tài)規(guī)劃 176
6.1.1 時(shí)間倒流，改變歷史 177
6.1.2 慎用貪心算法 177
6.1.3 強(qiáng)者恒強(qiáng)，弱者恒弱——最優(yōu)子結(jié)構(gòu) 178
6.2　智能的語言翻譯——編輯距離 178
6.2.1 設(shè)計(jì)語言翻譯系統(tǒng) 179
6.2.2 考慮最后一次編輯情況 180
6.2.3 自下而上進(jìn)行距離編輯 186
6.3　智能的電梯——電梯優(yōu)化 196
6.3.1 設(shè)計(jì)智能電梯 196
6.3.2 先考慮最后一次電梯停留的情況 197
6.3.3 自下而上計(jì)算電梯的停留過程 200
6.4　名字的相似度——最長公共子序列 208
6.4.1 外國人名的相似度 208
6.4.2 考慮最后一個(gè)字符比較情況 209
6.4.3 自下而上進(jìn)行距離編輯 213
第7章 回溯法 219
7.1　現(xiàn)代計(jì)算機(jī)的福音——回溯法 220
7.1.1 讓猴子打出《莎士比亞全集》 220
7.1.2 一條路走到黑——深度遍歷 221
7.1.3 亂花漸欲迷人眼——搜索中的剪枝 223
7.2　不能攻擊的皇后——8個(gè)皇后問題 224
7.2.1 一山不容二虎 224
7.2.2 如何設(shè)計(jì)8個(gè)皇后的解向量 226
7.2.3 搜索過程中的剪枝 228
7.3　絕望的小老鼠——迷宮中的小老鼠 241
7.3.1 上帝視角幫助小老鼠 241
7.3.2 小老鼠如何進(jìn)行搜索 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　一步一個(gè)腳印——分支限界 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