孫秀洋

第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章 陣列 34
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 平衡二叉樹 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 構造一棵平衡二叉搜尋樹 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 平方數 402
11.19 單詞拆分 405
11.19.1 回溯演算法 406
11.19.2 背包問題 407
11.20 買賣股票的 時機 410
11.20.1 暴力枚舉 410
11.20.2 貪心演算法 411
11.20.3 動態規劃 411
11.21 買賣股票的 時機II 414
11.22 買賣股票的 時機III 416
11.23 買賣股票的 時機IV 420
11.24 買賣股票時機（含冷凍期） 423
11.25 買賣股票的 時機（含手續費） 426
11.26 長遞增子序列 428
11.27 長連續遞增序列 430
11.27.1 動態規劃 430
11.27.2 貪心演算法 432
11.28 長重複子陣列 433
11.29 長公共子序列 436
11.30 不相交的線 438
11.31 子序和 440
11.32 判斷子序列 441
11.33 不同的子序列 444
11.34 兩個字串的刪除操作 447
11.35 編輯距離 450
11.36 回文子串 453
11.36.1 動態規劃 453
11.36.2 雙指針法 456
11.37 長回文子序列 457
11.38 本章小結