劍指Offer（專項突破版）：資料結構與演算法名企面試題精講

本書全面、系統地總結了在準備程式師面試過程中的資料結構與演算法。本書首先詳細討論整數、數組、鏈表、字符串、哈希表、棧、佇列、二叉樹、堆和首碼樹等常用的資料結構，然後深入討論二分查找、排序、回溯法、動態規劃和圖搜索等算法。除了介紹相應的基礎知識，每章還通過大量的高頻面試題系統地總結了各種資料結構與演算法的應用場景及解題技巧。

本書適合所有正在準備面試的程式師閱讀。無論是電腦相關專業的應屆畢業生還是初入職場的程式師，本書總結的資料結構和演算法的基礎知識及解題經驗都不僅可以幫助他們提高準備面試的效率，還可以增加他們通過面試的成功率。
 

第1章 整數 1
1.1 整數的基礎知識 1
1.2 二進位 4
1.3 本章小結 13

第2章 陣列 14
2.1 陣列的基礎知識 14
2.2 雙指針 15
2.3 累加陣列數位求子陣列之和 22
2.4 本章小結 28

第3章 字串 30
3.1 字串的基礎知識 30
3.2 雙指針 31
3.3 回文字串 41
3.4 本章小結 45

第4章 鏈表 46
4.1 鏈表的基礎知識 46
4.2 哨兵節點 47
4.3 雙指針 50
4.4 反轉鏈表 58
4.5 雙向鏈表和迴圈鏈表 66
4.6 本章小結 71

第5章 雜湊表 73
5.1 雜湊表的基礎知識 73
5.2 雜湊表的設計 74
5.3 雜湊表的應用 82
5.4 本章小結 91

第6章 棧 92
6.1 棧的基礎知識 92
6.2 棧的應用 93
6.3 本章小結 108

第7章 佇列 109
7.1 佇列的基礎知識 109
7.2 佇列的應用 110
7.3 二叉樹的廣度優先搜索 114
7.4 本章小結 125

第8章 樹 126
8.1 樹的基礎知識 126
8.2 二叉樹的深度優先搜索 127
8.3 二叉搜尋樹 141
8.4 TreeSet和TreeMap的應用 153
8.5 本章小結 160

第9章 堆 161
9.1 堆的基礎知識 161
9.2 堆的應用 165
9.3 本章小結 172

第10章 首碼樹 174
10.1 首碼樹的基礎知識 174
10.2 首碼樹的應用 179
10.3 本章小結 191

第11章 二分查找 192
11.1 二分查找的基礎知識 192
11.2 在排序陣列中二分查找 193
11.3 在數值範圍內二分查找 201
11.4 本章小結 205

第12章 排序 206
12.1 排序的基礎知識 206
12.2 計數排序 208
12.3 快速排序 211
12.4 歸併排序 215
12.5 本章小結 222

第13章 回溯法 224
13.1 回溯法的基礎知識 224
13.2 集合的組合、排列 226
13.3 回溯法解決其他類型問題 235
13.4 本章小結 239

第14章 動態規劃 241
14.1 動態規劃的基礎知識 241
14.2 單序列問題 248
14.3 雙序列問題 266
14.4 矩陣路徑問題 281
14.5 背包問題 293
14.6 本章小結 303

第15章 圖 305
15.1 圖的基礎知識 305
15.2 圖的搜索 307
15.3 拓撲排序 333
15.4 並查集 342
15.5 本章小結 354