算法大爆炸：面試通關步步為營

目 錄
上篇 數據結構與算法基礎
第 1 章 線性結構 ........................................................................................................... 2
1.1 數組 ........................................................................................................................ 2
1.1.1 數組的基本概念 ......................................................................................... 2
1.1.2 數組的定義 ................................................................................................. 3
1.1.3 數組的基本操作 ......................................................................................... 5
1.1.4 數組的性能分析 ....................................................................................... 11
1.1.5 案例分析 ................................................................................................... 12
1.2 鏈表 ...................................................................................................................... 19
1.2.1 鏈表的基本概念 ....................................................................................... 19
1.2.2 鏈表的定義 ............................................................................................... 20
1.2.3 鏈表的基本操作 ....................................................................................... 21
1.2.4 鏈表的性能分析 ....................................................................................... 27
1.2.5 不同形態的鏈表結構 ............................................................................... 28
1.2.6 案例分析 ................................................................................................... 29
1.3 棧 .......................................................................................................................... 38
1.3.1 棧的基本概念 ........................................................................................... 38
1.3.2 棧的定義 ................................................................................................... 38
1.3.3 棧的基本操作 ........................................................................................... 40
1.3.4 案例分析 ................................................................................................... 44
1.4 隊列 ...................................................................................................................... 50
1.4.1 隊列的基本概念 ....................................................................................... 50
1.4.2 隊列的定義 ............................................................................................... 50VI ∣
1.4.3 隊列的基本操作 ....................................................................................... 52
1.4.4 雙端隊列 ................................................................................................... 56
1.4.5 實戰分析 ................................................................................................... 56
第 2 章 樹結構 ............................................................................................................. 64
2.1 樹的基本概念 ...................................................................................................... 64
2.2 二叉樹 .................................................................................................................. 65
2.3 二叉樹的遍歷 ...................................................................................................... 68
2.4 創建二叉樹 .......................................................................................................... 71
2.5 二叉排序樹與 AVL 樹 ......................................................................................... 76
2.6 案例分析 .............................................................................................................. 81
第 3 章 圖結構 ............................................................................................................. 89
3.1 圖的基本概念 ...................................................................................................... 89
3.2 圖的存儲形式 ...................................................................................................... 92
3.3 鄰接表的實現 ...................................................................................................... 94
3.4 圖的遍歷 .............................................................................................................. 97
3.5 案例分析 ............................................................................................................ 103
第 4 章 排序與查找 .................................................................................................... 109
4.1 直接插入排序 .................................................................................................... 109
4.2 冒泡排序 ............................................................................................................ 112
4.3 簡單選擇排序 .................................................................................................... 114
4.4 快速排序 ............................................................................................................ 117
4.5 希爾排序 ............................................................................................................ 120
4.6 堆排序 ................................................................................................................ 122
4.7 各種排序算法的比較 ........................................................................................ 129
4.8 折半查找算法 .................................................................................................... 130
4.9 案例分析 ............................................................................................................ 132
第 5 章 窮舉法 ........................................................................................................... 139
5.1 窮舉法的基本思想 ............................................................................................ 139
5.2 案例分析 ............................................................................................................ 142
第 6 章 遞歸算法 ....................................................................................................... 149
6.1 遞歸算法的基本思想 ........................................................................................ 149
6.2 案例分析 ............................................................................................................ 150
第 7 章 貪心算法 ....................................................................................................... 159
7.1 貪心算法的基本思想 ........................................................................................ 159
7.2 案例分析 ............................................................................................................ 160
第 8 章 動態規劃 ....................................................................................................... 168
8.1 動態規劃算法的基本思想 ................................................................................ 168
8.2 案例分析 ............................................................................................................ 173
第 9 章 回溯法 ........................................................................................................... 185
9.1 回溯法的基本思想 ............................................................................................ 185
9.2 案例分析 ............................................................................................................ 188
下篇 大廠經典面試題詳解
第 10 章 數組和字符串類面試題 ................................................................................ 200
10.1 數組元素的奇偶重排 ...................................................................................... 200
10.2 不改變順序的數組元素奇偶重排................................................................... 203
10.3 有序數組的兩數之和 ...................................................................................... 206
10.4 三數之和 .......................................................................................................... 209
10.5 兩個有序數組的交集 ...................................................................................... 214
11.6 最長公共前綴問題........................................................................................... 219
10.7 最長公共子串問題 .......................................................................................... 221
10.8 長度最小的連續子數組 .................................................................................. 224
10.9 最長無重復子串 .............................................................................................. 232
10.10 刪除字符數組中特定字符 ............................................................................ 236
10.11 最短連續子數組問題 ..................................................................................... 240
10.12 字符數組的內容重排 .................................................................................... 242
10.13 字符串數組類面試題解題技巧 .................................................................... 246
第 11 章 線性結構類面試題 ....................................................................................... 249
11.1 約瑟夫環 .......................................................................................................... 249
11.2 單鏈表的逆置 .................................................................................................. 253
11.3 判斷鏈表中是否存在循環結構 ....................................................................... 256
11.4 判斷兩個鏈表是否相交 ................................................................................... 260
11.5 判斷迴文鏈表 .................................................................................................. 265
11.6 最小棧問題 ...................................................................................................... 269
11.7 每日溫度 .......................................................................................................... 275
11.8 LRU 緩存的設計.............................................................................................. 281
11.9 線性結構類面試題解題技巧 ........................................................................... 291
第 12 章 二叉樹類面試題 ........................................................................................... 293
12.1 完全二叉樹的判定 .......................................................................................... 293
12.2 二叉樹節點的最大距離 .................................................................................. 298
12.3 打印二叉樹中的重復子樹 .............................................................................. 302
12.4 還原二叉樹 ...................................................................................................... 307
12.5 二叉樹類面試題解題技巧 .............................................................................. 312
第 13 章 遞歸和動態規劃系列面試題 ......................................................................... 315
13.1 分解質因數 ...................................................................................................... 315
13.2 撥號盤字母組合 .............................................................................................. 317
13.3 組合的總和 ...................................................................................................... 322
13.4 在大矩陣中找 k ............................................................................................... 327
13.5 跳躍游戲 .......................................................................................................... 332
13.6 機器人的最小路徑長度 .................................................................................. 336
13.7 聰明的偵探 ...................................................................................................... 342
第 14 章 窮舉法和回溯法系列面試題 ......................................................................... 347
14.1 數組元素之差的最小值 .................................................................................. 347
14.2 數的分組問題 .................................................................................................. 350
14.3 最佳的碰面地點 .............................................................................................. 354
14.4 多點共線問題 .................................................................................................. 360
14.5 復原 IP 地址 ..................................................................................................... 369
14.6 矩陣中的相鄰數 .............................................................................................. 372
14.7 被包圍的區域 .................................................................................................. 377
第 15 章 其他類型算法面試題 .................................................................................... 382
15.1 相差多少天 ...................................................................................................... 382
15.2 萬年歷 .............................................................................................................. 386
15.3 1 的數量 ........................................................................................................... 389
15.4 找出人群中唯一的“單身者” ...................................................................... 392
15.5 找出人群中 3 個“單身者”中的任意一個 ................................................... 393
15.6 空瓶換汽水問題 .............................................................................................. 397
15.7 漁夫捕魚問題 .................................................................................................. 399
15.8 親密數 .............................................................................................................. 401
15.9 篩選出 100 以內的素數 .................................................................................. 403
15.10 尋找醜數 ........................................................................................................ 405
15.11 組成最小的數 ................................................................................................ 410
15.12 數字翻譯器 .................................................................................................... 413
15.13 計算 π 值 ........................................................................................................ 416