算法訓(xùn)練營：提高篇（全彩版）

定　價：￥128.00

作　者：	陳小玉
出版社：	電子工業(yè)出版社
叢編項：
標　簽：	暫缺

購買這本書可以去

當當網(wǎng) (￥121.60)

ISBN：	9787121490729	出版時間：	2024-11-01	包裝：	平裝-膠訂
開本：	16開	頁數(shù)：		字數(shù)：

內(nèi)容簡介

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

作者簡介

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

圖書目錄

第1章 STL 1
1.1 deque（雙端隊列） 1
訓(xùn)練度度熊學隊列 1
1.2 priority_queue（優(yōu)先隊列） 4
訓(xùn)練1 第k大的數(shù) 4
訓(xùn)練2 表演評分 6
1.3 bitset（位圖） 7
1.3.1 定義和初始化 8
1.3.2 基本操作 9
訓(xù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ù)據(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 簡單的整數(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)計單詞數(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)練雙重隊列 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 時空局部性的原理 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 超強記憶 159
第5章圖論提高 169
5.1 連通圖與強連通圖 169
5.2 橋與割點 170
5.3 雙連通分量的縮點 171
5.4 Tarjan算法 172
5.4.1 無向圖的橋 173
5.4.2 無向圖的割點 174
5.4.3 有向圖的強連通分量 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 重型運輸 211
訓(xùn)練2 貨幣兌換 212
訓(xùn)練3 蟲洞 214
6.3 拓撲排序 216
訓(xùn)練1 家族樹 220
訓(xùn)練2 標簽球 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ù)獨游戲 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章動態(tài)規(guī)劃提高 260
8.1 樹形動態(tài)規(guī)劃 260
訓(xùn)練1 戰(zhàn)略游戲 260
訓(xùn)練2 工人請愿書 262
8.2 狀態(tài)壓縮動態(tài)規(guī)劃 264
訓(xùn)練1 旅行商問題 265
訓(xùn)練2 玉米田 269
8.3 動態(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)隊列優(yōu)化 272
訓(xùn)練1 最長公共上升子序列 273
訓(xùn)練2 滑動窗口 275