第1章技術(shù)面試的方法論1
1.1 一道亞馬遜面試題的情景分析1
1.1.1 暴力枚舉法2
1.1.2 分而治之法4
1.1.3 最優(yōu)解法6
1.1.4 解題流程總結(jié)7
1.2 面試的流程，心態(tài)建設(shè)，相關(guān)準(zhǔn)備8
1.2.1 面試前流程8
1.2.2 簡歷的制作10
1.2.3 有效的面試策略11
1.2.4 編碼實(shí)現(xiàn)12
1.2.5 面試過程中的交流要點(diǎn)13
1.3 知己知彼，百戰(zhàn)不殆從面試官角度看面試14
1.3.1 如何進(jìn)行一場良好的面試15
1.3.2 面試官如何主導(dǎo)面試流程17
1.3.3 面試官如何評估候選人17
第2章算法面試的技術(shù)路線圖19
2.1 算法面試中的數(shù)據(jù)結(jié)構(gòu)19
2.1.1 基礎(chǔ)數(shù)據(jù)類型20
2.1.2 數(shù)組與字符串21
2.1.3 鏈表21
2.1.4 堆棧22
2.1.5 二叉樹22
2.1.6 堆23
2.1.7 哈希表23
2.2 算法的設(shè)計模式24
2.2.1 排序24
2.2.2 遞歸26
2.2.3 分而治之27
2.2.4 動態(tài)規(guī)劃29
2.2.5 貪婪算法29
2.2.6 逐步改進(jìn)29
2.2.7 排除法30
2.3 抽象分析模式30
2.3.1 樣例覆蓋31
2.3.2 小量數(shù)據(jù)推導(dǎo)31
2.3.3 簡單方案的逐步改進(jìn)32
2.3.4 問題還原33
2.3.5 圖論模擬34
第3章基礎(chǔ)數(shù)據(jù)類型的算法分析35
3.1 基礎(chǔ)數(shù)據(jù)類型中二進(jìn)制位的操作算法35
3.1.1 整型變量值互換35
3.1.2 常用的二進(jìn)制位操作36
3.1.3 解析一道二進(jìn)制操作相關(guān)算法面試題37
3.1.4 總結(jié)40
3.2 用二進(jìn)制操作求解集合所有子集40
3.2.1 題目描述40
3.2.2 算法描述40
3.2.3 代碼實(shí)現(xiàn)41
3.2.4 算法分析43
3.3 使用二進(jìn)制求解最大公約數(shù)43
3.3.1 題目描述43
3.3.2 算法描述45
3.3.3 代碼實(shí)現(xiàn)47
3.3.4 算法分析49
3.4 素數(shù)判定50
3.4.1 題目描述50
3.4.2 算法描述50
3.4.3 代碼實(shí)現(xiàn)52
3.4.4 算法分析53
3.5 判斷矩形交集54
3.5.1 題目描述54
3.5.2 算法描述54
3.5.3 代碼實(shí)現(xiàn)56
3.6 數(shù)字與字符串相互轉(zhuǎn)化，簡單題目的隱藏陷阱58
3.6.1 題目描述58
3.6.2 算法描述58
3.6.3 代碼實(shí)現(xiàn)59
3.6.4 算法分析60
3.7 Elias Gamma編碼算法62
3.7.1 題目描述62
3.7.2 算法描述63
3.7.3 代碼實(shí)現(xiàn)63
3.7.4 算法分析66
3.8 整型的二進(jìn)制乘法67
3.8.1 題目描述67
3.8.2 算法描述67
3.8.3 代碼實(shí)現(xiàn)69
3.8.4 算法分析73
第4章數(shù)組和字符串74
4.1 數(shù)組的定位排序74
4.1.1 題目描述74
4.1.2 算法描述75
4.1.3 代碼實(shí)現(xiàn)76
4.1.4 算法分析78
4.2 在整型數(shù)組中構(gòu)建元素之和能整除數(shù)組長度的子集78
4.2.1 題目描述78
4.2.2 算法描述78
4.2.3 代碼實(shí)現(xiàn)79
4.2.4 算法分析82
4.3 計算等價類82
4.3.1 題目描述82
4.3.2 算法描述83
4.3.3 代碼實(shí)現(xiàn)85
4.3.4 代碼分析86
4.4 大型整數(shù)相乘87
4.4.1 題目描述87
4.4.2 算法描述87
4.4.3 代碼實(shí)現(xiàn)88
4.4.4 代碼分析91
4.5 數(shù)組的序列變換92
4.5.1 題目描述92
4.5.2 算法描述92
4.5.3 代碼實(shí)現(xiàn)94
4.5.4 代碼分析96
4.6 字符串的旋轉(zhuǎn)96
4.6.1 題目描述96
4.6.2 算法描述96
4.6.3 代碼實(shí)現(xiàn)97
4.6.4 代碼分析99
4.7 二維數(shù)組的啟發(fā)式搜索算法99
4.7.1 題目描述99
4.7.2 算法描述99
4.7.3 代碼實(shí)現(xiàn)100
4.7.4 代碼分析101
4.8 二維數(shù)組的旋轉(zhuǎn)遍歷102
4.8.1 題目描述102
4.8.2 算法描述102
4.8.3 代碼實(shí)現(xiàn)104
4.8.4 代碼分析105
4.9 矩陣的90旋轉(zhuǎn)105
4.9.1 題目描述106
4.9.2 算法描述106
4.9.3 代碼實(shí)現(xiàn)107
4.9.4 代碼分析109
4.10 游程編碼109
4.10.1 題目描述110
4.10.2 算法描述110
4.10.3 代碼實(shí)現(xiàn)110
4.10.4 代碼分析112
4.11 字符串中單詞的逆轉(zhuǎn)113
4.11.1 題目描述113
4.11.2 算法描述113
4.11.3 代碼實(shí)現(xiàn)114
4.11.4 代碼分析115
4.12 Rabin-Karp字符串匹配算法115
4.12.1 題目描述115
4.12.2 算法描述115
4.12.3 代碼實(shí)現(xiàn)118
4.12.4 代碼分析120
4.13 用有限狀態(tài)自動機(jī)匹配字符串120
4.13.1 題目描述120
4.13.2 算法描述121
4.13.3 代碼實(shí)現(xiàn)124
4.13.4 代碼分析127
4.14 KMP算法字符串匹配算法的創(chuàng)意巔峰127
4.14.1 題目描述127
4.14.2 算法描述127
4.14.3 代碼實(shí)現(xiàn)129
4.14.4 代碼分析131
4.15 正則表達(dá)式引擎的設(shè)計和實(shí)施132
4.15.1 題目描述132
4.15.2 算法描述133
4.15.3 代碼實(shí)現(xiàn)138
4.15.4 代碼分析178
第5章隊列和鏈表179
5.1 遞歸式實(shí)現(xiàn)鏈表快速倒轉(zhuǎn)179
5.1.1 題目描述179
5.1.2 算法描述180
5.1.3 代碼實(shí)現(xiàn)181
5.1.4 代碼分析184
5.2 鏈表成環(huán)檢測184
5.2.1 題目描述185
5.2.2 算法描述185
5.2.3 代碼實(shí)現(xiàn)186
5.2.4 代碼分析189
5.3 在O(1)時間內(nèi)刪除單鏈表非末尾節(jié)點(diǎn)190
5.3.1 題目描述190
5.3.2 算法描述190
5.3.3 代碼實(shí)現(xiàn)191
5.3.4 代碼分析192
5.4 獲取重合列表的第一個相交節(jié)點(diǎn)192
5.4.1 題目描述193
5.4.2 算法描述193
5.4.3 代碼實(shí)現(xiàn)194
5.4.4 代碼分析196
5.5 單向鏈表的奇偶排序196
5.5.1 題目描述196
5.5.2 算法描述196
5.5.3 代碼實(shí)現(xiàn)198
5.5.4 代碼分析199
5.6 雙指針單向鏈表的自我復(fù)制199
5.6.1 題目描述200
5.6.2 算法描述200
5.6.3 代碼實(shí)現(xiàn)202
5.6.4 代碼分析206
5.7 利用鏈表層級打印二叉樹206
5.7.1 題目描述206
5.7.2 算法描述206
5.7.3 代碼實(shí)現(xiàn)207
5.7.4 代碼分析209
第6章堆棧和隊列210
6.1 利用堆棧計算逆向波蘭表達(dá)式210
6.1.1 題目描述210
6.1.2 算法描述210
6.1.3 代碼實(shí)現(xiàn)211
6.1.4 代碼分析213
6.2 計算堆棧當(dāng)前元素最大值213
6.2.1 題目描述213
6.2.2 算法描述213
6.2.3 代碼實(shí)現(xiàn)214
6.2.4 代碼分析216
6.3 使用堆棧判斷括號匹配216
6.3.1 題目描述216
6.3.2 算法描述216
6.3.3 代碼實(shí)現(xiàn)217
6.3.4 代碼分析218
6.4 使用堆棧解決漢諾塔問題218
6.4.1 題目描述218
6.4.2 算法描述219
6.4.3 代碼實(shí)現(xiàn)219
6.4.4 代碼分析222
6.5 堆棧元素的在線排序222
6.5.1 題目描述223
6.5.2 算法描述223
6.5.3 代碼實(shí)現(xiàn)224
6.5.4 代碼分析225
6.6 計算滑動窗口內(nèi)的最大網(wǎng)絡(luò)流量225
6.6.1 題目描述226
6.6.2 算法描述226
6.6.3 代碼實(shí)現(xiàn)231
6.6.4 代碼分析234
6.7 使用堆棧模擬隊列234
6.7.1 題目描述235
6.7.2 算法描述235
6.7.3 代碼實(shí)現(xiàn)235
6.7.4 代碼分析236
第7章二叉樹238
7.1 二叉樹的平衡性檢測238
7.1.1 題目描述239
7.1.2 算法描述239
7.1.3 代碼實(shí)現(xiàn)239
7.1.4 代碼分析242
7.2 鏡像二叉樹的檢測242
7.2.1 題目描述243
7.2.2 算法描述243
7.2.3 代碼實(shí)現(xiàn)244
7.2.4 代碼分析246
7.3 二叉樹的Morris遍歷法247
7.3.1 題目描述247
7.3.2 算法描述247
7.3.3 代碼實(shí)現(xiàn)250
7.3.4 代碼分析251
7.4 使用前序遍歷和中序遍歷重構(gòu)二叉樹252
7.4.1 題目描述252
7.4.2 算法描述253
7.4.3 代碼實(shí)現(xiàn)254
7.4.4 代碼分析256
7.5 逆時針打印二叉樹外圍邊緣256
7.5.1 題目描述256
7.5.2 算法描述257
7.5.3 代碼實(shí)現(xiàn)257
7.5.4 代碼分析259
7.6 尋找兩個二叉樹節(jié)點(diǎn)的最近共同祖先259
7.6.1 題目描述260
7.6.2 算法描述260
7.6.3 代碼實(shí)現(xiàn)260
7.6.4 代碼分析264
7.7 設(shè)計搜索輸入框的輸入提示功能264
7.7.1 題目描述264
7.7.2 算法描述264
7.7.3 代碼實(shí)現(xiàn)265
7.7.4 代碼分析269
第8章堆270
8.1 使用堆排序?qū)崿F(xiàn)系統(tǒng)Timer機(jī)制270
8.1.1 題目描述270
8.1.2 算法描述270
8.1.3 代碼實(shí)現(xiàn)273
8.1.4 代碼分析279
8.2 波浪形數(shù)組的快速排序法279
8.2.1 題目描述279
8.2.2 算法描述280
8.2.3 代碼實(shí)現(xiàn)281
8.2.4 代碼分析287
8.3 快速獲取數(shù)組中點(diǎn)的相鄰區(qū)域點(diǎn)287
8.3.1 題目描述287
8.3.2 算法描述287
8.3.3 代碼實(shí)現(xiàn)289
8.3.4 代碼分析292
第9章二分查找法293
9.1 隱藏在《編程珠璣》中20年的bug293
9.1.1 題目描述294
9.1.2 算法描述294
9.1.3 代碼實(shí)現(xiàn)295
9.1.4 代碼分析297
9.2 在lg(k)時間內(nèi)查找兩個排序數(shù)組合并后第k小元素297
9.2.1 題目描述297
9.2.2 算法描述297
9.2.3 代碼實(shí)現(xiàn)299
9.2.4 代碼分析301
9.3 二分查找法尋求數(shù)組截斷點(diǎn)302
9.3.1 題目描述302
9.3.2 算法描述302
9.3.3 代碼實(shí)現(xiàn)304
9.3.4 代碼分析306
9.4 在雙升序數(shù)組中快速查找給定值306
9.4.1 題目描述307
9.4.2 算法描述307
9.4.3 代碼實(shí)現(xiàn)307
9.4.4 代碼分析309
第10章圖論310
10.1 地圖著色問題310
10.1.1 問題描述310
10.1.2 算法描述310
10.1.3 代碼實(shí)現(xiàn)311
10.1.4 代碼分析315
10.2 迪杰斯特拉最短路徑算法316
10.2.1 題目描述316
10.2.2 算法描述316
10.2.3 代碼實(shí)現(xiàn)319
10.2.4 代碼分析326
10.3 使用深度優(yōu)先搜索解決容器倒水問題327
10.3.1 問題描述327
10.3.2 算法描述327
10.3.3 代碼實(shí)現(xiàn)329
10.3.4 代碼分析333
第11章貪婪算法335
11.1 最小生成樹335
11.1.1 題目描述335
11.1.2 算法描述336
11.1.3 代碼實(shí)現(xiàn)339
11.1.4 代碼分析344
11.2 霍夫曼編碼344
11.2.1 題目描述345
11.2.2 算法描述345
11.2.3 代碼實(shí)現(xiàn)347
11.2.4 代碼分析349
11.3 離散點(diǎn)集的最大覆蓋率問題350
11.3.1 題目描述350
11.3.2 算法描述351
11.3.3 代碼實(shí)現(xiàn)352
11.3.4 代碼分析355
第12章動態(tài)規(guī)劃356
12.1 鋼管最優(yōu)切割方案356
12.1.1 問題描述357
12.1.2 算法描述357
12.1.3 代碼實(shí)現(xiàn)358
12.1.4 代碼分析360
12.2 查找最大共同子串361
12.2.1 問題描述362
12.2.2 算法描述362
12.2.3 代碼實(shí)現(xiàn)364
12.2.4 代碼分析366
12.3 將最大共同子串算法的空間復(fù)雜度從O(n2)改進(jìn)為O(n)366
12.3.1 問題描述367
12.3.2 算法描述367
12.3.3 代碼實(shí)現(xiàn)368
12.3.4 代碼分析371
書單推薦
