算法訓練營：提高篇（全彩版）

定　價：￥128.00

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

購買這本書可以去

當當網 (￥121.60)

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

內容簡介

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

作者簡介

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

圖書目錄

第1章 STL 1
1.1 deque（雙端隊列） 1
訓練度度熊學隊列 1
1.2 priority_queue（優(yōu)先隊列） 4
訓練1 第k大的數 4
訓練2 表演評分 6
1.3 bitset（位圖） 7
1.3.1 定義和初始化 8
1.3.2 基本操作 9
訓練集合運算 10
1.4 set、multiset（集合、多重集合） 12
訓練1 集合合并 13
訓練2 并行處理 14
1.5 map、multimap（映射、多重映射） 16
訓練1 硬木種類 18
訓練2 水果 19
1.6 STL中的常用函數 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
訓練1 中位數 25
訓練2 字謎 26
第2章實用的數據結構 28
2.1 并查集 28
訓練1 暢通工程 33
訓練2 方塊棧 35
2.2 倍增、稀疏表（ST）、區(qū)間最值查詢（RMQ） 38
2.2.1 倍增 38
2.2.2 稀疏表 39
2.2.3 區(qū)間最值查詢 41
訓練1 區(qū)間最值差 41
訓練2 最頻繁值 42
2.3 最近公共祖先（LCA） 45
2.3.1 暴力搜索法 46
2.3.2 樹上倍增法 47
2.3.3 在線區(qū)間最值查詢算法 51
2.3.4 離線Tarjan算法 53
訓練1 最近公共祖先 57
訓練2 樹上距離 59
2.4 樹狀數組 61
2.4.1 一維樹狀數組 61
2.4.2 多維樹狀數組 67
訓練1 數星星 68
訓練2 矩形區(qū)域查詢 70
2.5 線段樹 71
2.5.1 基本操作 71
2.5.2 懶操作 76
訓練1 敵兵布陣 80
訓練2 簡單的整數問題 83
第3章查找算法 85
3.1 散列表 85
3.1.1 散列函數 86
3.1.2 開放地址法 88
3.1.3 鏈地址法 96
3.1.4 建立公共溢出區(qū) 98
3.1.5 散列查找及其性能分析 98
訓練雪花 99
3.2 字符串模式匹配 100
3.2.1 BF算法 101
3.2.2 KMP算法 103
訓練1 統(tǒng)計單詞數 109
訓練2 字符串匹配 111
3.3 字典樹（Trie樹） 112
3.3.1 創(chuàng)建 113
3.3.2 查找 115
3.3.3 應用 116
訓練單詞翻譯 116
第4章平衡樹 118
4.1 樹高與性能 118
4.2 平衡二叉搜索樹（AVL樹） 119
4.2.1 調整平衡的方法 120
4.2.2 插入 122
4.2.3 創(chuàng)建 126
4.2.4 刪除 128
訓練雙重隊列 131
4.3 樹堆（Treap） 134
4.3.1 右旋和左旋 135
4.3.2 插入 136
4.3.3 刪除 138
4.3.4 前驅 140
4.3.5 后繼 140
訓練少林功夫 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
訓練1 玩鏈子 152
訓練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
訓練1 道路建設 177
訓練2 校園網絡 180
第6章圖論算法 183
6.1 最小生成樹 183
6.1.1 Prim算法 184
6.1.2 Kruskal算法 191
訓練1 叢林之路 195
訓練2 聯(lián)網 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
訓練1 重型運輸 211
訓練2 貨幣兌換 212
訓練3 蟲洞 214
6.3 拓撲排序 216
訓練1 家族樹 220
訓練2 標簽球 222
6.4 關鍵路徑 224
訓練1 指令安排 232
訓練2 家務瑣事 233
第7章搜索算法提高 235
7.1 剪枝優(yōu)化 235
訓練1 數獨游戲 235
訓練2 小木棍 238
7.2 嵌套廣度優(yōu)先搜索 240
訓練推箱子 240
7.3 雙向廣度優(yōu)先搜索 244
訓練魔鬼Ⅱ 244
7.4 啟發(fā)式搜索 246
7.4.1 A*算法 247
7.4.2 IDA*算法 247
訓練1 八數碼問題 248
訓練2 第k短路徑 257
第8章動態(tài)規(guī)劃提高 260
8.1 樹形動態(tài)規(guī)劃 260
訓練1 戰(zhàn)略游戲 260
訓練2 工人請愿書 262
8.2 狀態(tài)壓縮動態(tài)規(guī)劃 264
訓練1 旅行商問題 265
訓練2 玉米田 269
8.3 動態(tài)規(guī)劃優(yōu)化 271
8.3.1 倍增優(yōu)化 272
8.3.2 數據結構優(yōu)化 272
8.3.3 單調隊列優(yōu)化 272
訓練1 最長公共上升子序列 273
訓練2 滑動窗口 275