算法筆記

第1章 如何使用本書 1
1.1 本書的基本內容 1
1.2 如何選擇編程語言和編譯器 1
1.3 在線評測系統 2
1.4 常見的評測結果 3
1.5 如何高效地做題 4
第2章 C/C++快速入門 5
2.1 基本數據類型 7
2.1.1 變量的定義 7
2.1.2 變量類型 7
2.1.3 強制類型轉換 11
2.1.4 符號常量和const常量 12
2.1.5 運算符 14
2.2 順序結構 17
2.2.1 賦值表達式 17
2.2.2 使用scanf和printf輸入/輸出 18
2.2.3 使用getchar和putchar輸入/輸出字符 23
2.2.4 註釋 24
2.2.5 typedef 24
2.2.6 常用math函數 25
2.3 選擇結構 28
2.3.1 if語句 28
2.3.2 if語句的嵌套 31
2.3.3 switch語句 32
2.4 循環結構 34
2.4.1 while語句 34
2.4.2 do while語句 35
2.4.3 for語句 36
2.4.4 break和continue語句 38
2.5 數組 39
2.5.1 一維數組 39
2.5.2 冒泡排序 41
2.5.3 二維數組 43
2.5.4 memset——對數組中每一個元素賦相同的值 46
2.5.5 字符數組 47
2.5.6 string.h頭文件 50
2.5.7 sscanf與sprintf 53
2.6 函數 55
2.6.1 函數的定義 55
2.6.2 再談main函數 58
2.6.3 以數組作為函數參數 58
2.6.4 函數的嵌套調用 59
2.6.5 函數的遞歸調用 60
2.7 指針 61
2.7.1 什麼是指針 61
2.7.2 指針變量 62
2.7.3 指針與數組 63
2.7.4 使用指針變量作為函數參數 65
2.7.5 引用 68
2.8 結構體（struct）的使用 70
2.8.1 結構體的定義 70
2.8.2 訪問結構體內的元素 71
2.8.3 結構體的初始化 72
2.9 補充 74
2.9.1 cin與cout 74
2.9.2 浮點數的比較 75
2.9.3 複雜度 78
2.10 黑盒測試 80
2.10.1 單點測試 80
2.10.2 多點測試 80
第3章 入門篇（1）——入門模擬 85
3.1 簡單模擬 85
3.2 查找元素 87
3.3 圖形輸出 89
3.4 日期處理 91
3.5 進制轉換 93
3.6 字符串處理 95
第4章 入門篇（2）——算法初步 99
4.1 排序 99
4.1.1 選擇排序 99
4.1.2 插入排序 100
4.1.3 排序題與sort函數的應用 101
4.2 散列 106
4.2.1 散列的定義與整數散列 106
4.2.2 字符串hash初步 109
4.3 遞歸 111
4.3.1 分治 111
4.3.2 遞歸 112
4.4 貪心 118
4.4.1 簡單貪心 118
4.4.2 區間貪心 122
4.5 二分 124
4.5.1 二分查找 124
4.5.2 二分法拓展 131
4.5.3 快速冪 134
4.6 two pointers 137
4.6.1 什麼是two pointers 137
4.6.2 歸併排序 139
4.6.3 快速排序 142
4.7 其他高效技巧與算法 146
4.7.1 打表 146
4.7.2 活用遞推 147
4.7.3 選擇算法 149
第5章 入門篇（3）——數學問題 152
5.1 簡單數學 152
5.2 大公約數與小公倍數 154
5.2.1 大公約數 154
5.2.2 小公倍數 156
5.3 分數的四則運算 156
5.3.1 分數的表示和化簡 157
5.3.2 分數的四則運算 157
5.3.3 分數的輸出 159
5.4 素數 159
5.4.1 素數的判斷 160
5.4.2 素數表的獲取 160
5.5 質因子分解 165
5.6 大整數運算 170
5.6.1 大整數的存儲 170
5.6.2 大整數的四則運算 171
5.7 擴展歐幾裏得算法 176
5.8 組合數 181
5.8.1 關於n!的一個問題 181
5.8.2 組合數的計算 183
第6章 C++標準模板庫（STL）介紹 191
6.1 vector的常見用法詳解 191
6.2 set的常見用法詳解 197
6.3 string的常見用法詳解 202
6.4 map的常用用法詳解 213
6.5 queue的常見用法詳解 218
6.6 priority_queue的常見用法詳解 221
6.7 stack的常見用法詳解 227
6.8 pair的常見用法詳解 230
6.9 algorithm頭文件下的常用函數 232
6.9.1 max、min和abs 232
6.9.2 swap 233
6.9.3 reverse 233
6.9.4 next_permutation 234
6.9.5 fill 235
6.9.6 sort 235
6.9.7 lower_bound和upper_bound 242
第7章 提高篇（1）——數據結構專題（1） 245
7.1 棧的應用 245
7.2 隊列的應用 251
7.3 鍊錶處理 253
7.3.1 鍊錶的概念 253
7.3.2 使用malloc函數或new運算符為鍊錶結點分配內存空間 254
7.3.3 鍊錶的基本操作 256
7.3.4 靜態鍊錶 260
第8章 提高篇（2）——搜索專題 269
8.1 深度優先搜索（DFS） 269
8.2 廣度優先搜索（BFS） 274
第9章 提高篇（3）——數據結構專題（2） 283
9.1 樹與二叉樹 283
9.1.1 樹的定義與性質 283
9.1.2 二叉樹的遞歸定義 284
9.1.3 二叉樹的存儲結構與基本操作 285
9.2 二叉樹的遍歷 289
9.2.1 先序遍歷 289
9.2.2 中序遍歷 290
9.2.3 後序遍歷 291
9.2.4 層序遍歷 292
9.2.5 二叉樹的靜態實現 298
9.3 樹的遍歷 302
9.3.1 樹的靜態寫法 302
9.3.2 樹的先根遍歷 303
9.3.3 樹的層序遍歷 303
9.3.4 從樹的遍歷看DFS與BFS 304
9.4 二叉查找樹（BST） 310
9.4.1 二叉查找樹的定義 310
9.4.2 二叉查找樹的基本操作 310
9.4.3 二叉查找樹的性質 314
9.5 平衡二叉樹（AVL樹） 319
9.5.1 平衡二叉樹的定義 319
9.5.2 平衡二叉樹的基本操作 320
9.6 並查集 328
9.6.1 並查集的定義 328
9.6.2 並查集的基本操作 328
9.6.3 路徑壓縮 330
9.7 堆 335
9.7.1 堆的定義與基本操作 335
9.7.2 堆排序 339
9.8 哈夫曼樹 342
9.8.1 哈夫曼樹 342
9.8.2 哈弗曼編碼 345
第10章 提高篇（4）——圖算法專題 347
10.1 圖的定義和相關術語 347
10.2 圖的存儲 348
10.2.1 鄰接矩陣 348
10.2.2 鄰接表 348
10.3 圖的遍歷 350
10.3.1 採用深度優先搜索（DFS）法遍歷圖 350
10.3.2 採用廣度優先搜索（BFS）法遍歷圖 359
10.4 短路徑 367
10.4.1 Dijkstra算法 367
10.4.2 Bellman-Ford算法和SPFA算法 391
10.4.3 Floyd算法 398
10.5 小生成樹 400
10.5.1 小生成樹及其性質 400
10.5.2 prim算法 401
10.5.3 kruskal算法 409
10.6 拓撲排序 414
10.6.1 有向無環圖 414
10.6.2 拓撲排序 415
10.7 關鍵路徑 417
10.7.1 AOV網和AOE網 417
10.7.2 長路徑 419
10.7.3 關鍵路徑 419
第11章 提高篇（5）——動態規劃專題 425
11.1 動態規劃的遞歸寫法和遞推寫法 425
11.1.1 什麼是動態規劃 425
11.1.2 動態規劃的遞歸寫法 425
11.1.3 動態規劃的遞推寫法 426
11.2 大連續子序列和 429
11.3 長不下降子序列（LIS） 432
11.4 長公共子序列（LCS） 434
11.5 長迴文子串 436
11.6 DAG長路 439
11.7 背包問題 442
11.7.1 多階段動態規劃問題 442
11.7.2 01背包問題 443
11.7.3 完全背包問題 446
11.8 總結 447
第12章 提高篇（6）——字符串專題 449
12.1 字符串hash進階 449
12.2 KMP算法 455
12.2.1 next數組 456
12.2.2 KMP算法 458
12.2.3 從有限狀態自動機的角度看待KMP算法 463
第13章 專題擴展 465
13.1 分塊思想 465
13.2 樹狀數組（BIT） 470
13.2.1 lowbit運算 470
13.2.2 樹狀數組及其應用 470
參考文獻 481