123,123,123

內(nèi)容簡(jiǎn)介

　　本書圖文并茂、通俗易懂，詳細(xì)講解常用的算法知識(shí)，又融入大量的競(jìng)賽實(shí)例和解題技巧，可幫助讀者熟練應(yīng)用各種算法解決實(shí)際問題。本書總計(jì)8章。第1章講解STL，涉及雙端隊(duì)列、優(yōu)先隊(duì)列、位圖、集合、映射和STL中的常用函數(shù)；第2章講解實(shí)用的數(shù)據(jù)結(jié)構(gòu)，涉及并查集、倍增、稀疏表、區(qū)間最值查詢、最近公共祖先、樹狀數(shù)組和線段樹；第3章講解查找算法，涉及散列表、字符串模式匹配和字典樹；第4章講解平衡樹，涉及樹高與性能、平衡二叉搜索樹、樹堆和伸展樹；第5章講解圖論提高方面的知識(shí)，涉及連通圖與強(qiáng)連通圖、橋與割點(diǎn)、雙連通分量的縮點(diǎn)和Tarjan算法；第6章講解圖論算法，涉及最小生成樹、最短路徑、拓?fù)渑判蚝完P(guān)鍵路徑；第7章講解搜索算法提高方面的知識(shí)，涉及剪枝優(yōu)化、嵌套廣度優(yōu)先搜索、雙向廣度優(yōu)先搜索和啟發(fā)式搜索；第8章講解動(dòng)態(tài)規(guī)劃提高方面的知識(shí)，涉及樹形動(dòng)態(tài)規(guī)劃、狀態(tài)壓縮動(dòng)態(tài)規(guī)劃和動(dòng)態(tài)規(guī)劃優(yōu)化。本書面向?qū)λ惴ǜ信d趣的讀者，無論是想扎實(shí)內(nèi)功或參加算法競(jìng)賽的學(xué)生，還是想進(jìn)入名企的學(xué)生、求職者，抑或是想提升核心競(jìng)爭(zhēng)力的在職人員，都可以參考本書。若讀者想系統(tǒng)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法，則可參考《算法訓(xùn)練營(yíng)：入門篇》（全彩版）和《算法訓(xùn)練營(yíng)：進(jìn)階篇》（全彩版）。

作者簡(jiǎn)介

　　陳小玉高級(jí)程序員，主要研究方向?yàn)樗惴▋?yōu)化和機(jī)器學(xué)習(xí)。出版著作有《趣學(xué)算法》《趣學(xué)數(shù)據(jù)結(jié)構(gòu)》《算法訓(xùn)練營(yíng)》，所教學(xué)生多次獲得ACM-ICPC、藍(lán)橋杯等算法競(jìng)賽獎(jiǎng)項(xiàng)。

圖書目錄

第1章 STL 1
1.1 deque（雙端隊(duì)列） 1
訓(xùn)練度度熊學(xué)隊(duì)列 1
1.2 priority_queue（優(yōu)先隊(duì)列） 4
訓(xùn)練1 第k大的數(shù) 4
訓(xùn)練2 表演評(píng)分 6
1.3 bitset（位圖） 7
1.3.1 定義和初始化 8
1.3.2 基本操作 9
訓(xùn)練集合運(yùn)算 10
1.4 set、multiset（集合、多重集合） 12
訓(xùn)練1 集合合并 13
訓(xùn)練2 并行處理 14
1.5 map、multimap（映射、多重映射） 16
訓(xùn)練1 硬木種類 18
訓(xùn)練2 水果 19
1.6 STL中的常用函數(shù) 21
1.6.1 fill() 21
1.6.2 nth_element() 22
1.6.3 lower_bound()、upper_bound() 23
1.6.4 next_permutation()、pre_permutation() 23
訓(xùn)練1 中位數(shù) 25
訓(xùn)練2 字謎 26
第2章實(shí)用的數(shù)據(jù)結(jié)構(gòu) 28
2.1 并查集 28
訓(xùn)練1 暢通工程 33
訓(xùn)練2 方塊棧 35
2.2 倍增、稀疏表（ST）、區(qū)間最值查詢（RMQ） 38
2.2.1 倍增 38
2.2.2 稀疏表 39
2.2.3 區(qū)間最值查詢 41
訓(xùn)練1 區(qū)間最值差 41
訓(xùn)練2 最頻繁值 42
2.3 最近公共祖先（LCA） 45
2.3.1 暴力搜索法 46
2.3.2 樹上倍增法 47
2.3.3 在線區(qū)間最值查詢算法 51
2.3.4 離線Tarjan算法 53
訓(xùn)練1 最近公共祖先 57
訓(xùn)練2 樹上距離 59
2.4 樹狀數(shù)組 61
2.4.1 一維樹狀數(shù)組 61
2.4.2 多維樹狀數(shù)組 67
訓(xùn)練1 數(shù)星星 68
訓(xùn)練2 矩形區(qū)域查詢 70
2.5 線段樹 71
2.5.1 基本操作 71
2.5.2 懶操作 76
訓(xùn)練1 敵兵布陣 80
訓(xùn)練2 簡(jiǎn)單的整數(shù)問題 83
第3章查找算法 85
3.1 散列表 85
3.1.1 散列函數(shù) 86
3.1.2 開放地址法 88
3.1.3 鏈地址法 96
3.1.4 建立公共溢出區(qū) 98
3.1.5 散列查找及其性能分析 98
訓(xùn)練雪花 99
3.2 字符串模式匹配 100
3.2.1 BF算法 101
3.2.2 KMP算法 103
訓(xùn)練1 統(tǒng)計(jì)單詞數(shù) 109
訓(xùn)練2 字符串匹配 111
3.3 字典樹（Trie樹） 112
3.3.1 創(chuàng)建 113
3.3.2 查找 115
3.3.3 應(yīng)用 116
訓(xùn)練單詞翻譯 116
第4章平衡樹 118
4.1 樹高與性能 118
4.2 平衡二叉搜索樹（AVL樹） 119
4.2.1 調(diào)整平衡的方法 120
4.2.2 插入 122
4.2.3 創(chuàng)建 126
4.2.4 刪除 128
訓(xùn)練雙重隊(duì)列 131
4.3 樹堆（Treap） 134
4.3.1 右旋和左旋 135
4.3.2 插入 136
4.3.3 刪除 138
4.3.4 前驅(qū) 140
4.3.5 后繼 140
訓(xùn)練少林功夫 141
4.4 伸展樹（Splay樹） 144
4.4.1 時(shí)空局部性的原理 144
4.4.2 右旋和左旋 145
4.4.3 伸展 146
4.4.4 查找 149
4.4.5 插入 150
4.4.6 分裂 150
4.4.7 合并 150
4.4.8 刪除 151
4.4.9 區(qū)間操作 151
4.4.10 算法分析 152
訓(xùn)練1 玩鏈子 152
訓(xùn)練2 超強(qiáng)記憶 159
第5章圖論提高 169
5.1 連通圖與強(qiáng)連通圖 169
5.2 橋與割點(diǎn) 170
5.3 雙連通分量的縮點(diǎn) 171
5.4 Tarjan算法 172
5.4.1 無向圖的橋 173
5.4.2 無向圖的割點(diǎn) 174
5.4.3 有向圖的強(qiáng)連通分量 175
訓(xùn)練1 道路建設(shè) 177
訓(xùn)練2 校園網(wǎng)絡(luò) 180
第6章圖論算法 183
6.1 最小生成樹 183
6.1.1 Prim算法 184
6.1.2 Kruskal算法 191
訓(xùn)練1 叢林之路 195
訓(xùn)練2 聯(lián)網(wǎng) 197
6.2 最短路徑 199
6.2.1 Dijkstra算法 199
6.2.2 Floyd算法 204
6.2.3 Bellman-Ford算法 208
6.2.4 SPFA算法 209
訓(xùn)練1 重型運(yùn)輸 211
訓(xùn)練2 貨幣兌換 212
訓(xùn)練3 蟲洞 214
6.3 拓?fù)渑判?216
訓(xùn)練1 家族樹 220
訓(xùn)練2 標(biāo)簽球 222
6.4 關(guān)鍵路徑 224
訓(xùn)練1 指令安排 232
訓(xùn)練2 家務(wù)瑣事 233
第7章搜索算法提高 235
7.1 剪枝優(yōu)化 235
訓(xùn)練1 數(shù)獨(dú)游戲 235
訓(xùn)練2 小木棍 238
7.2 嵌套廣度優(yōu)先搜索 240
訓(xùn)練推箱子 240
7.3 雙向廣度優(yōu)先搜索 244
訓(xùn)練魔鬼Ⅱ 244
7.4 啟發(fā)式搜索 246
7.4.1 A*算法 247
7.4.2 IDA*算法 247
訓(xùn)練1 八數(shù)碼問題 248
訓(xùn)練2 第k短路徑 257
第8章動(dòng)態(tài)規(guī)劃提高 260
8.1 樹形動(dòng)態(tài)規(guī)劃 260
訓(xùn)練1 戰(zhàn)略游戲 260
訓(xùn)練2 工人請(qǐng)?jiān)笗?262
8.2 狀態(tài)壓縮動(dòng)態(tài)規(guī)劃 264
訓(xùn)練1 旅行商問題 265
訓(xùn)練2 玉米田 269
8.3 動(dòng)態(tài)規(guī)劃優(yōu)化 271
8.3.1 倍增優(yōu)化 272
8.3.2 數(shù)據(jù)結(jié)構(gòu)優(yōu)化 272
8.3.3 單調(diào)隊(duì)列優(yōu)化 272
訓(xùn)練1 最長(zhǎng)公共上升子序列 273
訓(xùn)練2 滑動(dòng)窗口 275