代碼隨想錄：跟著Carl學(xué)算法

目錄

第1章 準(zhǔn)備面試要知己知彼 1
1.1 面試官為什么要考查算法 1
1.2 編程語(yǔ)言 2
1.2.1 學(xué)好算法之前更要學(xué)好編程語(yǔ)言 2
1.2.2 代碼規(guī)范 2
1.3 如何寫(xiě)簡(jiǎn)歷 5
1.3.1 簡(jiǎn)歷模板 5
1.3.2 謹(jǐn)慎使用“精通” 5
1.3.3 拿不準(zhǔn)的內(nèi)容不要寫(xiě)在簡(jiǎn)歷上 5
1.3.4 項(xiàng)目經(jīng)驗(yàn)應(yīng)該如何寫(xiě) 6
1.3.5 博客的重要性 7
1.4 企業(yè)技術(shù)面試的流程 7
1.4.1 一面——機(jī)試面 7
1.4.2 二面——基礎(chǔ)算法面 8
1.4.3 三面——綜合技術(shù)面 8
1.4.4 四面——技術(shù)leader面 8
1.4.5 五面——HR面 9
1.5 本章小結(jié) 10
第2章 程序的性能分析 11
2.1 時(shí)間復(fù)雜度分析 11
2.1.1 什么是時(shí)間復(fù)雜度 11
2.1.2 如何描述時(shí)間復(fù)雜度 12
2.1.3 遞歸算法的時(shí)間復(fù)雜度分析 14
2.2 程序的運(yùn)行時(shí)間 17
2.2.1 超時(shí)是怎么回事 17
2.2.2 從硬件配置看計(jì)算機(jī)的性能 18
2.2.3 測(cè)試計(jì)算機(jī)的運(yùn)行速度 18
2.3 編程語(yǔ)言的內(nèi)存管理 20
2.3.1 C 的內(nèi)存管理 21
2.3.2 如何計(jì)算程序占用多少內(nèi)存 22
2.3.3 內(nèi)存對(duì)齊 22
2.4 空間復(fù)雜度分析 24
2.4.1 什么是空間復(fù)雜度 24
2.4.2 遞歸算法的空間復(fù)雜度分析 25
2.4.3 以空間換時(shí)間是常見(jiàn)的優(yōu)化思路 32
2.5 本章小結(jié) 33
第3章 數(shù)組 34
3.1 數(shù)組理論基礎(chǔ) 34
3.2 二分查找 36
3.2.1 二分法寫(xiě)法（一） 37
3.2.2 二分法寫(xiě)法（二） 38
3.3 移除元素 39
3.3.1 暴力解法 40
3.3.2 雙指針?lè)?41
3.4 長(zhǎng)度小的子數(shù)組 42
3.4.1 暴力解法 42
3.4.2 滑動(dòng)窗口 43
3.5 這個(gè)循環(huán)轉(zhuǎn)懵了很多人 45
3.5.1 循環(huán)不變量 45
3.5.2 代碼實(shí)現(xiàn) 46
3.6 本章小結(jié) 48
第4章 鏈表 49
4.1 鏈表理論基礎(chǔ) 49
4.1.1 鏈表的類(lèi)型 49
4.1.2 鏈表的存儲(chǔ)方式 50
4.1.3 鏈表的定義 51
4.1.4 鏈表的操作 52
4.1.5 性能分析 52
4.2 用虛擬頭節(jié)點(diǎn)會(huì)方便得多 53
4.3 鏈表常見(jiàn)的六個(gè)操作 57
4.4 反轉(zhuǎn)鏈表 60
4.4.1 雙指針?lè)?60
4.4.2 遞歸法 61
4.5 刪除倒數(shù)第n個(gè)節(jié)點(diǎn) 62
4.6 環(huán)形鏈表 64
4.6.1 判斷鏈表是否有環(huán) 65
4.6.2 尋找環(huán)的入口 66
4.7 本章小結(jié) 69
第5章 哈希表 70
5.1 哈希表理論基礎(chǔ) 70
5.1.1 哈希函數(shù) 71
5.1.2 哈希碰撞 71
5.1.3 常見(jiàn)的三種哈希結(jié)構(gòu) 73
5.2 有效的字母異位詞 74
5.3 兩個(gè)數(shù)組的交集 76
5.4 兩數(shù)之和 78
5.5 四數(shù)相加 80
5.6 三數(shù)之和 81
5.6.1 哈希解法 81
5.6.2 雙指針?lè)?82
5.7 四數(shù)之和 85
5.8 本章小結(jié) 87
第6章 字符串 88
6.1 字符串與數(shù)組的區(qū)別 88
6.2 反轉(zhuǎn)字符串 89
6.3 反轉(zhuǎn)字符串II 90
6.4 反轉(zhuǎn)字符串里的單詞 92
6.5 KMP算法理論基礎(chǔ) 96
6.5.1 什么是KMP算法 96
6.5.2 什么是前綴表 96
6.5.3 為什么一定要用前綴表 97
6.5.4 如何計(jì)算前綴表 98
6.5.5 時(shí)間復(fù)雜度分析 100
6.6 使用KMP匹配字符串 101
6.6.1 構(gòu)造next數(shù)組 101
6.6.2 使用next數(shù)組做匹配 103
6.6.3 前綴表統(tǒng)一減一的代碼實(shí)現(xiàn) 104
6.6.4 前綴表（不減一）的代碼實(shí)現(xiàn) 105
6.7 找到重復(fù)的子字符串 107
6.8 本章小結(jié) 109
第7章 棧與隊(duì)列 110
7.1 棧與隊(duì)列理論基礎(chǔ) 110
7.2 用棧組成隊(duì)列 112
7.3 用隊(duì)列組成棧 114
7.3.1 使用兩個(gè)隊(duì)列實(shí)現(xiàn)棧 115
7.3.2 使用一個(gè)隊(duì)列實(shí)現(xiàn)棧 117
7.4 匹配括號(hào) 118
7.5 逆波蘭表達(dá)式 120
7.6 滑動(dòng)窗口值 122
7.7 前k個(gè)高頻元素 126
7.8 接雨水 129
7.8.1 雙指針解法 130
7.8.2 動(dòng)態(tài)規(guī)劃解法 132
7.8.3 單調(diào)棧解法 133
7.9 本章小結(jié) 137
第8章 二叉樹(shù) 139
8.1 二叉樹(shù)理論基礎(chǔ) 139
8.1.1 二叉樹(shù)的種類(lèi) 139
8.1.2 二叉樹(shù)的存儲(chǔ)方式 141
8.1.3 二叉樹(shù)的遍歷方式 142
8.1.4 二叉樹(shù)的定義 143
8.2 前中后序的遞歸遍歷 144
8.3 前中后序的迭代遍歷 146
8.3.1 前序遍歷 146
8.3.2 中序遍歷 147
8.3.3 后序遍歷 148
8.4 前、中、后序統(tǒng)一迭代法 149
8.5 二叉樹(shù)的層序遍歷 152
8.6 反轉(zhuǎn)二叉樹(shù) 155
8.6.1 遞歸法 156
8.6.2 迭代法 156
8.7 對(duì)稱(chēng)二叉樹(shù) 158
8.7.1 遞歸法 159
8.7.2 迭代法 162
8.8 二叉樹(shù)的深度 164
8.8.1 遞歸法 165
8.8.2 迭代法 166
8.9 二叉樹(shù)的小深度 167
8.9.1 遞歸法 168
8.9.2 迭代法 170
8.10 平衡二叉樹(shù) 170
8.10.1 遞歸法 173
8.10.2 迭代法 175
8.11 二叉樹(shù)的所有路徑 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 構(gòu)造一棵二叉樹(shù) 189
8.13.1 使用中序與后序遍歷序列構(gòu)造二叉樹(shù) 189
8.13.2 使用前序與中序遍歷序列構(gòu)造二叉樹(shù) 195
8.13.3 相關(guān)思考 197
8.14 合并兩棵二叉樹(shù) 197
8.14.1 遞歸 198
8.14.2 迭代法 200
8.15 在二叉搜索樹(shù)中尋找節(jié)點(diǎn) 201
8.15.1 遞歸法 202
8.15.2 迭代法 203
8.16 驗(yàn)證二叉搜索樹(shù) 204
8.16.1 遞歸法 205
8.16.2 迭代法 207
8.17 二叉搜索樹(shù)的小差 208
8.17.1 遞歸法 208
8.17.2 迭代法 209
8.18 二叉搜索樹(shù)中的眾數(shù) 210
8.18.1 遞歸法 211
8.18.2 迭代法 215
8.19 二叉樹(shù)的近公共祖先 216
8.19.1 普通二叉樹(shù) 216
8.19.2 二叉搜索樹(shù) 221
8.20 在二叉搜索樹(shù)中插入一個(gè)節(jié)點(diǎn) 224
8.20.1 遞歸法 225
8.20.2 迭代法 227
8.21 在二叉搜索樹(shù)中刪除一個(gè)節(jié)點(diǎn) 228
8.21.1 遞歸法 228
8.21.2 迭代法 230
8.22 修剪二叉搜索樹(shù) 231
8.22.1 遞歸法 232
8.22.2 迭代法 234
8.23 構(gòu)造一棵平衡二叉搜索樹(shù) 235
8.23.1 遞歸法 236
8.23.2 迭代法 238
8.24 本章小結(jié) 239
第9章 回溯算法 240
9.1 回溯算法理論基礎(chǔ) 240
9.1.1 什么是回溯算法 240
9.1.2 回溯法的性能 240
9.1.3 回溯法可以解決的問(wèn)題 240
9.1.4 如何理解回溯法 241
9.1.5 回溯法模板 241
9.2 組合問(wèn)題 243
9.2.1 回溯算法 244
9.2.2 剪枝優(yōu)化 248
9.3 組合總和（一） 250
9.3.1 回溯算法 251
9.3.2 剪枝優(yōu)化 254
9.4 電話號(hào)碼的字母組合 255
9.5 組合總和（二） 260
9.5.1 回溯算法 261
9.5.2 剪枝優(yōu)化 263
9.6 組合總和（三） 265
9.7 分割回文串 270
9.8 復(fù)原IP地址 274
9.9 子集問(wèn)題（一） 279
9.10 子集問(wèn)題（二） 281
9.11 遞增子序列 284
9.11.1 回溯算法 285
9.11.2 哈希優(yōu)化 287
9.12 排列問(wèn)題（一） 288
9.13 排列問(wèn)題（二） 291
9.13.1 回溯算法 291
9.13.2 拓展 293
9.14 N皇后問(wèn)題 296
9.15 解數(shù)獨(dú) 301
9.15.1 回溯算法 302
9.15.2 判斷棋盤(pán)是否合法 304
9.16 本章小結(jié) 305
第10章 貪心算法 306
10.1 貪心算法理論基礎(chǔ) 306
10.1.1 什么是貪心 306
10.1.2 貪心的套路 306
10.2 分發(fā)餅干 307
10.3 擺動(dòng)序列 309
10.4 子序和 312
10.5 買(mǎi)賣(mài)股票的時(shí)機(jī)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 分發(fā)糖果 327
10.10 檸檬水找零 330
10.11 用少數(shù)量的箭射爆氣球 332
10.12 合并區(qū)間 335
10.13 單調(diào)遞增的數(shù)字 338
10.13.1 暴力解法 338
10.13.2 貪心解法 339
10.14 本章小結(jié) 340
第11章 動(dòng)態(tài)規(guī)劃 341
11.1 動(dòng)態(tài)規(guī)劃理論基礎(chǔ) 341
11.1.1 動(dòng)態(tài)規(guī)劃題目的解題步驟 341
11.1.2 動(dòng)態(tài)規(guī)劃應(yīng)該如何排查問(wèn)題 342
11.2 斐波那契數(shù) 343
11.2.1 動(dòng)態(tài)規(guī)劃解法 344
11.2.2 遞歸解法 345
11.3 爬樓梯 346
11.4 使用花費(fèi)爬樓梯 349
11.5 不同路徑（一） 353
11.5.1 深度優(yōu)先搜索 354
11.5.2 動(dòng)態(tài)規(guī)劃 355
11.5.3 數(shù)論方法 356
11.6 不同路徑（二） 358
11.7 整數(shù)拆分 361
11.7.1 動(dòng)態(tài)規(guī)劃 362
11.7.2 貪心算法 364
11.8 不同的二叉搜索樹(shù) 364
11.9 0-1背包理論基礎(chǔ) 369
11.9.1 二維dp數(shù)組 370
11.9.2 一維dp數(shù)組 375
11.10 分割等和子集 379
11.11 目標(biāo)和 382
11.12 一和零 385
11.13 完全背包理論基礎(chǔ) 388
11.14 零錢(qián)兌換（一） 392
11.15 拼湊一個(gè)正整數(shù) 395
11.16 多步爬樓梯 398
11.17 零錢(qián)兌換（二） 399
11.18 完全平方數(shù) 402
11.19 單詞拆分 405
11.19.1 回溯算法 406
11.19.2 背包問(wèn)題 407
11.20 買(mǎi)賣(mài)股票的時(shí)機(jī) 410
11.20.1 暴力枚舉 410
11.20.2 貪心算法 411
11.20.3 動(dòng)態(tài)規(guī)劃 411
11.21 買(mǎi)賣(mài)股票的時(shí)機(jī)II 414
11.22 買(mǎi)賣(mài)股票的時(shí)機(jī)III 416
11.23 買(mǎi)賣(mài)股票的時(shí)機(jī)IV 420
11.24 買(mǎi)賣(mài)股票時(shí)機(jī)（含冷凍期） 423
11.25 買(mǎi)賣(mài)股票的時(shí)機(jī)（含手續(xù)費(fèi)） 426
11.26 長(zhǎng)遞增子序列 428
11.27 長(zhǎng)連續(xù)遞增序列 430
11.27.1 動(dòng)態(tài)規(guī)劃 430
11.27.2 貪心算法 432
11.28 長(zhǎng)重復(fù)子數(shù)組 433
1