代碼隨想錄 — 跟著 Carl 學算法

孫秀洋（@程序員Carl）
哈爾濱工業大學計算機科學與技術專業碩士，先後在騰訊和百度從事技術研發，微信公眾號“代碼隨想錄”作者，對數據結構與算法有深刻理解，擅長將一個個算法串聯在一起並用通俗易懂的方式講解出來。

第1章  準備面試要知己知彼 1
1.1  面試官為什麼要考查算法 1
1.2  編程語言 2
1.2.1  學好算法之前更要學好編程語言 2
1.2.2  代碼規範 2
1.3  如何寫簡歷 5
1.3.1  簡歷模板 5
1.3.2  謹慎使用“精通” 5
1.3.3  拿不准的內容絕#對不要寫在簡歷上 5
1.3.4  項目經驗應該如何寫 6
1.3.5  博客的重要性 7
1.4  企業技術面試的流程 7
1.4.1  一面——機試面 7
1.4.2  二面——基礎算法面 8
1.4.3  三面——綜合技術面 8
1.4.4  四面——技術leader面 8
1.4.5  五面——HR面 9
1.5  本章小結 10

第2章  程序的性能分析 11
2.1  時間複雜度分析 11
2.1.1  什麼是時間複雜度 11
2.1.2  如何描述時間複雜度 12
2.1.3  遞歸算法的時間複雜度分析 14
2.2  程序的運行時間 17
2.2.1  超時是怎麼回事 17
2.2.2  從硬件配置看計算機的性能 18
2.2.3  測試計算機的運行速度 18
2.3  編程語言的內存管理 20
2.3.1  C++的內存管理 21
2.3.2  如何計算程序佔用多少內存 22
2.3.3  內存對齊 22
2.4  空間複雜度分析 24
2.4.1  什麼是空間複雜度 24
2.4.2  遞歸算法的空間複雜度分析 25
2.4.3  以空間換時間是常見的優化思路 32
2.5  本章小結 33

第3章  數組 3
3.1  數組理論基礎 34
3.2  二分查找 36
3.2.1  二分法寫法（一） 37
3.2.2  二分法寫法（二） 38
3.3  移除元素 39
3.3.1  暴力解法 40
3.3.2  雙指針法 41
3.4  長度#小的子數組 42
3.4.1  暴力解法 42
3.4.2  滑動窗口 43
3.5  這個循環轉懵了很多人 45
3.5.1  循環不變量 45
3.5.2  代碼實現 46
3.6  本章小結 48

第4章  鍊錶 49
4.1  鍊錶理論基礎 49
4.1.1  鍊錶的類型 49
4.1.2  鍊錶的存儲方式 50
4.1.3  鍊錶的定義 51
4.1.4  鍊錶的操作 52
4.1.5  性能分析 52
4.2  用虛擬頭節點會方便得多 53
4.3  鍊錶常見的六個操作 57
4.4  反轉鍊錶 60
4.4.1  雙指針法 60
4.4.2  遞歸法 61
4.5  刪除倒數第n個節點 62
4.6  環形鍊錶 64
4.6.1  判斷鍊表是否有環 65
4.6.2  尋找環的入口 66
4.7  本章小結 69

第5章  哈希表 70
5.1  哈希表理論基礎 70
5.1.1  哈希函數 71
5.1.2  哈希碰撞 71
5.1.3  常見的三種哈希結構 73
5.2  有效的字母異位詞 74
5.3  兩個數組的交集 76
5.4  兩數之和 78
5.5  四數相加 80
5.6  三數之和 81
5.6.1  哈希解法 81
5.6.2  雙指針法 82
5.7  四數之和 85
5.8  本章小結 87

第6章  字符串 88
6.1  字符串與數組的區別 88
6.2  反轉字符串 89
6.3  反轉字符串II 90
6.4  反轉字符串裡的單詞 92
6.5  KMP算法理論基礎 96
6.5.1  什麼是KMP算法 96
6.5.2  什麼是前綴表 96
6.5.3  為什麼一定要用前綴表 97
6.5.4  如何計算前綴表 98
6.5.5  時間複雜度分析 100
6.6  使用KMP匹配字符串 101
6.6.1  構造next數組 101
6.6.2  使用next數組做匹配 103
6.6.3  前綴表統一減一的代碼實現 104
6.6.4  前綴表（不減一）的代碼實現 105
6.7  找到重複的子字符串 107
6.8  本章小結 109

第7章  棧與隊列 110
7.1  棧與隊列理論基礎 110
7.2  用棧組成隊列 112
7.3  用隊列組成棧 114
7.3.1  使用兩個隊列實現棧 115
7.3.2  使用一個隊列實現棧 117
7.4  匹配括號 118
7.5  逆波蘭表達式 120
7.6  滑動窗口#大值 122
7.7  前k個高頻元素 126
7.8  接雨水 129
7.8.1  雙指針解法 130
7.8.2  動態規劃解法 132
7.8.3  單調棧解法 133
7.9  本章小結 137

第8章  二叉樹 139
8.1  二叉樹理論基礎 139
8.1.1  二叉樹的種類 139
8.1.2  二叉樹的存儲方式 141
8.1.3  二叉樹的遍歷方式 142
8.1.4  二叉樹的定義 143
8.2  前中後序的遞歸遍歷 144
8.3  前中後序的迭代遍歷 146
8.3.1  前序遍歷 146
8.3.2  中序遍歷 147
8.3.3  後序遍歷 148
8.4  前、中、後序統一迭代法 149
8.5  二叉樹的層序遍歷 152
8.6  反轉二叉樹 155
8.6.1  遞歸法 156
8.6.2  迭代法 156
8.7  對稱二叉樹 158
8.7.1  遞歸法 159
8.7.2  迭代法 162
8.8  二叉樹的#大深度 164
8.8.1  遞歸法 165
8.8.2  迭代法 166
8.9  二叉樹的#小深度 167
8.9.1  遞歸法 168
8.9.2  迭代法 170
8.10  ping衡二叉樹 170
8.10.1  遞歸法 173
8.10.2  迭代法 175
8.11  二叉樹的所有路徑 176
8.11.1  遞歸法 177
8.11.2  迭代法 182
8.12  路徑總和 183
8.12.1  遞歸法 183
8.12.2  迭代法 186
8.12.3  路徑總和II 187
8.13  構造一棵二叉樹 189
8.13.1  使用中序與後序遍歷序列構造二叉樹 189
8.13.2  使用前序與中序遍歷序列構造二叉樹 195
8.13.3  相關思考 197
8.14  合併兩棵二叉樹 197
8.14.1  遞歸 198
8.14.2  迭代法 200
8.15  在二叉搜索樹中尋找節點 201
8.15.1  遞歸法 202
8.15.2  迭代法 203
8.16  驗證二叉搜索樹 204
8.16.1  遞歸法 205
8.16.2  迭代法 207
8.17  二叉搜索樹的#小絕#對差 208
8.17.1  遞歸法 208
8.17.2  迭代法 209
8.18  二叉搜索樹中的眾數 210
8.18.1  遞歸法 211
8.18.2  迭代法 215
8.19  二叉樹的#近公共祖先 216
8.19.1  普通二叉樹 216
8.19.2  二叉搜索樹 221
8.20  在二叉搜索樹中插入一個節點 224
8.20.1  遞歸法 225
8.20.2  迭代法 227
8.21  在二叉搜索樹中刪除一個節點 228
8.21.1  遞歸法 228
8.21.2  迭代法 230
8.22  修剪二叉搜索樹 231
8.22.1  遞歸法 232
8.22.2  迭代法 234
8.23  構造一棵ping衡二叉搜索樹 235
8.23.1  遞歸法 236
8.23.2  迭代法 238
8.24  本章小結 239

第9章  回溯算法 240
9.1  回溯算法理論基礎 240
9.1.1  什麼是回溯算法 240
9.1.2  回溯法的性能 240
9.1.3  回溯法可以解決的問題 240
9.1.4  如何理解回溯法 241
9.1.5  回溯法模板 241
9.2  組合問題 243
9.2.1  回溯算法 244
9.2.2  剪枝優化 248
9.3  組合總和（一） 250
9.3.1  回溯算法 251
9.3.2  剪枝優化 254
9.4  電話號碼的字母組合 255
9.5  組合總和（二） 260
9.5.1  回溯算法 261
9.5.2  剪枝優化 263
9.6  組合總和（三） 265
9.7  分割回文串 270
9.8  復原IP地址 274
9.9  子集問題（一） 279
9.10  子集問題（二） 281
9.11  遞增子序列 284
9.11.1  回溯算法 285
9.11.2  哈希優化 287
9.12  排列問題（一） 288
9.13  排列問題（二） 291
9.13.1  回溯算法 291
9.13.2  拓展 293
9.14  N皇后問題 296
9.15  解數獨 301
9.15.1  回溯算法 302
9.15.2  判斷棋盤是否合法 304
9.16  本章小結 305

第10章  貪心算法 306
10.1  貪心算法理論基礎 306
10.1.1  什麼是貪心 306
10.1.2  貪心的套路 306
10.2  分發餅乾 307
10.3  擺動序列 309
10.4  #大子序和 312
10.5  買賣股票的#佳時機II 314
10.6  跳躍遊戲 316
10.7  跳躍遊戲II 318
10.7.1  貪心解法（一） 320
10.7.2  貪心解法（二） 320
10.8  加油站 322
10.8.1  暴力解法 323
10.8.2  貪心解法（一） 324
10.8.3  貪心解法（二） 325
10.9  分發糖果 327
10.10  檸檬水找零 330
10.11  用#少數量的箭射爆氣球 332
10.12  合併區間 335
10.13  單調遞增的數字 338
10.13.1  暴力解法 338
10.13.2  貪心解法 339
10.14  本章小結 340

第11章  動態規劃 341
11.1  動態規劃理論基礎 341
11.1.1  動態規劃題目的解題步驟 341
11.1.2  動態規劃應該如何排查問題 342
11.2  斐波那契數 343
11.2.1  動態規劃解法 344
11.2.2  遞歸解法 345
11.3  爬樓梯 346
11.4  使用#低花費爬樓梯 349
11.5  不同路徑（一） 353
11.5.1  深度優先搜索 354
11.5.2  動態規劃 355
11.5.3  數論方法 356
11.6  不同路徑（二） 358
11.7  整數拆分 361
11.7.1  動態規劃 362
11.7.2  貪心算法 364
11.8  不同的二叉搜索樹 364
11.9  0-1背包理論基礎 369
11.9.1  二維dp數組 370
11.9.2  一維dp數組 375
11.10  分割等和子集 379
11.11  目標和 382
11.12  一和零 385
11.13  完全背包理論基礎 388
11.14  零錢兌換（一） 392
11.15  拼湊一個正整數 395
11.16  多步爬樓梯 398
11.17  零錢兌換（二） 399
11.18  完全ping方數 402
11.19  單