《算法訓練營：海量圖解+競賽刷題（進階篇）》是2021年電子工業出版社出版書籍，作者是陳小玉。
基本介紹
- 中文名：算法訓練營：海量圖解+競賽刷題（進階篇）
- 作者：陳小玉
- 出版社：電子工業出版社
- 出版時間：2021年
- 頁數：656 頁
- 定價：139.8 元
- 開本：16 開
- ISBN：9787121408861
內容簡介,圖書目錄,
內容簡介
本書以海量圖解的形式，詳細講解常用的數據結構與算法，並結合競賽實例引導讀者進行刷題實戰。通過對本書的學習，讀者將掌握22種高級數據結構、7種動態規划算法、5種動態規劃最佳化技巧，以及5種網路流算法，並熟練套用各種算法解決實際問題。 本書總計8章。第1章講解實用數據結構，包括並查集、優先佇列；第2章講解區間信息維護與查詢，包括倍增、ST、RMQ、LCA、樹狀數組、線段樹和分塊；第3章講解字元串處理，包括字典樹、AC自動機和後綴數組；第4章講解樹上操作問題，包括點分治、邊分治、樹鏈剖分和動態樹；第5章講解各種平衡二叉樹，包括Treap、伸展樹和SBT；第6章講解數據結構進階，包括KD樹、左偏樹、跳躍表、樹套樹和可持久化數據結構；第7章講解動態規劃及其最佳化，包括背包問題、線性DP、區間DP、樹形DP、數位DP、狀態壓縮DP、插頭DP和動態規劃最佳化方法；第8章講解網路流問題，包括常用網路流算法、二分圖最大匹配、最大流最小割定理和最小費用最大流。本書對每個算法都進行詳細圖解並搭配競賽實例，重點講解如何分析問題、最佳化算法，以期讀者在短時間內掌握該算法並進行刷題實戰。
圖書目錄
第1章 實用數據結構 1
1.1 並查集 1
原理 並查集詳解 1
訓練1 暢通工程 6
訓練2 方塊棧 7
訓練3 食物鏈 10
訓練4 幫派 16
1.2 優先佇列 19
原理1 優先佇列的實現原理 19
原理2 優先佇列詳解 23
訓練1 第k大的數 26
訓練2 圍欄修復 27
訓練3 表演評分 29
訓練4 叢林探險 30
第2章 區間信息維護與查詢 33
2.1 倍增、ST、RMQ 33
原理1 倍增 33
原理2 ST 34
原理3 RMQ 36
訓練1 區間最值差 36
訓練2 最頻繁值 37
訓練3 最小分段數 40
訓練4 二維區間最值差 41
2.2 最近公共祖先LCA 43
原理1 暴力搜尋法 44
原理2 樹上倍增法 45
原理3 線上RMQ算法 49
原理4 Tarjan算法 51
訓練1 最近公共祖先 55
訓練2 樹上距離 57
訓練3 距離查詢 59
訓練4 城市之間的聯繫 60
2.3 樹狀數組 62
原理1 一維樹狀數組 62
原理2 多維樹狀數組 67
訓練1 數星星 69
訓練2 公路交叉數 71
訓練3 子樹查詢 74
訓練4 矩形區域查詢 76
2.4 線段樹 78
原理1 線段樹的基本操作 78
原理2 線段樹中的“懶操作” 83
訓練1 敵兵布陣 87
訓練2 簡單的整數問題 89
訓練3 數據結構難題 91
訓練4 顏色統計 97
2.5 分塊 102
原理 分塊詳解 102
訓練1 簡單的整數問題 105
訓練2 數字序列 106
訓練3 區間最值差 107
訓練4 超級馬里奧 109
訓練5 序列操作 111
第3章 字元串處理 115
3.1 字典樹 115
原理 字典樹詳解 115
訓練1 單詞翻譯 120
訓練2 電話表 122
訓練3 統計難題 123
訓練4 彩色的木棒 124
訓練5 最長xor路徑 127
3.2 AC自動機 129
原理 AC自動機詳解 129
訓練1 關鍵字檢索 132
訓練2 病毒侵襲 134
訓練3 DNA序列 136
訓練4 單詞情結 140
3.3 後綴數組 145
原理1 基數排序 145
原理2 後綴數組詳解 152
訓練1 牛奶模式 169
訓練2 口吃的外星人 171
訓練3 音樂主題 173
訓練4 星際迷航 175
