演算法訓練營：提高篇 (全彩版)

陳小玉

演算法訓練營：提高篇 (全彩版)

買這商品的人也買了...

簡體館年度書展｜現貨2書79折3書75折 詳見活動內容 »

簡體館年度書展｜現貨2書79折3書75折 詳見活動內容 »

相關主題

商品描述

本書圖文並茂、通俗易懂，詳細講解常用的演算法知識，
又融入大量的競賽實例和解題技巧，可幫助讀者熟練應用各種演算法解決實際問題。
本書總計8章。
第1章講解STL，涉及雙端佇列、優先權佇列、位圖、集合、映射和STL中的常用函數；
第2章講解實用的資料結構，涉及並查集、倍增、稀疏表、區間最值查詢、最近公共祖先、樹狀數組和線段樹；
第3章講解查找演算法，涉及散列表、字串模式比對和字典樹；
第4章講解平衡樹，涉及樹高與性能、平衡二元搜尋樹、樹堆和伸展樹；
第5章說明圖論提高方面的知識，涉及連通圖與強連通圖、橋與割點、雙連通分量的縮點和Tarjan演算法；
第6章講解圖論演算法，涉及最小生成樹、最短路徑、拓樸排序和關鍵路徑；
第7章講解搜尋演算法提升方面的知識，涉及剪枝優化、嵌套廣度優先搜尋、雙向廣度優先搜尋和啟發式搜尋；
第8章說明動態規劃提升方面的知識，涉及樹狀動態規劃、狀態壓縮動態規劃和動態規劃最佳化。
本書面向對演算法有興趣的讀者，無論是想紮實內功或參加演算法競賽的學生，
還是想進入名企的學生、求職者，抑或是想提升核心競爭力的在職人員，都可以參考本書。
若讀者想系統學習資料結構與演算法，可參考《演算法訓練營：入門篇》（全彩版）與《演算法訓練營：進階篇》（全彩版）。

目錄大綱

 

第1章 STL 1
1.1 deque（雙端隊列） 1
訓練 度熊學隊列 1
1.2 priority_queue（先隊列） 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）、區間值查詢（RMQ） 38
2.2.1 倍增 38
2.2.2 稀疏表 39
2.2.3 區間值查詢 41
訓練1 區間值差 41
訓練2 頻繁值 42
2.3 近公共祖先（LCA） 45
2.3.1 暴力搜索法 46
2.3.2 樹上倍增法 47
2.3.3 線上區間值查詢演算法 51
2.3.4 離線Tarjan演算法 53
訓練1 近公共祖先 57
訓練2 樹上距離 59
2.4 樹狀數組 61
2.4.1 一維樹狀數組 61
2.4.2 多維樹狀數組 67
訓練1 數星星 68
訓練2 矩形區域查詢 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 建立公共溢位區 98
3.1.5 散列查找及其效能分析 98
訓練 雪花 99
3.2 字串模式比對 100
3.2.1 BF算法 101
3.2.2 KMP演算法 103
訓練1 統計字數 109
訓練2 字串匹配 111
3.3 字典樹（Trie樹） 112
3.3.1 創建 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 創建 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 區間作 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 聯網 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 剪枝化 235
訓練1 數獨遊戲 235
訓練2 小木棍 238
7.2 嵌套廣度先搜尋 240
訓練 推箱子 240
7.3 雙向廣度先搜尋 244
訓練 魔鬼Ⅱ 244
7.4 啟發式搜尋 246
7.4.1 A*演算法 247
7.4.2 IDA*演算法 247
訓練1 八數碼問題 248
訓練2 第k短路徑 257

 第8章 動態規劃提升 260
8.1 樹狀動態規劃 260
訓練1 戰略遊戲 260
訓練2 工人請願書 262
8.2 狀態壓縮動態規劃 264
訓練1 旅行商問題 265
訓練2 玉米田 269
8.3 動態規劃化 271
8.3.1 倍增化 272
8.3.2 資料結構化 272
8.3.3 單調隊列化 272
訓練1 長公共上升子序列 273
訓練2 滑動視窗 275

類似商品