目錄


第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
1