前言 6

第 1 章 時(shí)間復(fù)雜度與空間復(fù)雜度 10

1.1 時(shí)間復(fù)雜度 10

1.2 空間復(fù)雜度 15

1.3 總結(jié) 17

1. 時(shí)間復(fù)雜度 17

2. 空間復(fù)雜度 18

第 2 章 排序算法 19

2.1 冒泡排序 20

2.2 選擇排序 27

2.3 插入排序 29

2.4 希爾排序 33

2.5 歸并排序 39

2.6 堆排序 47

2.7 快速排序 47

2.7.1 快速排序的常用方法 47

2.7.2 快速排序的優(yōu)化 52

2.7.3 非遞歸實(shí)現(xiàn) 54

2.7.4 算法比較 55

2.7.5 快速排序的一些應(yīng)用 55

2.8 計(jì)數(shù)排序 56

2.9 桶排序 58

2.10 基數(shù)排序 61

2.10.1 LSD 基數(shù)排序 61

2.10.2 MSD 基數(shù)排序 64

2.10.3 字符串使用基數(shù)排序?qū)崿F(xiàn)字典排序 66

2.11 總結(jié) 68

2.11.1 算法使用場(chǎng)景 69

第 3 章 線性結(jié)構(gòu) 71

3.1 數(shù)據(jù)結(jié)構(gòu)的分類 71

3.2 數(shù)組 73

3.3 鏈表 75

3.3.1 單向鏈表 75

3.3.2 雙向鏈表 78

3.3.3 有序鏈表 80

3.3.4 循環(huán)雙向鏈表 83

3.3.5 鏈表排序 88

3.4 棧 96

3.4.1 棧的特點(diǎn)和相關(guān)概念 96

3.4.2 棧相關(guān)的方法 98

3.4.3 棧的應(yīng)用場(chǎng)景 99

3.5 隊(duì)列 106

3.5.1 隊(duì)列的常用方法 107

3.5.2 隊(duì)列的典型應(yīng)用 108

3.6 散列簡述 109

3.6.1 散列函數(shù) 109

3.6.2 散列沖突的解決方案 112

3.6.3 散列的應(yīng)用 121

3.7 位圖 124

3.7.1 位圖簡述 124

3.7.2 位圖的應(yīng)用 127

3.8 塊狀鏈表 129

3.8.1 塊狀鏈表簡介 129

3.8.2 塊狀鏈表的操作 130

3.9 總結(jié) 136

第 4 章 散列詳談 139

4.1 散列的定義 139

4.2 常見的散列算法 139

4.3 散列沖突的解決方案 141

4.3.1 開散列方法 142

4.3.2 閉散列方法 144

4.4 散列的應(yīng)用 146

4.4.1 數(shù)組去重 146

4.4.2 求只出現(xiàn)一次的數(shù)字 147

4.4.3 兩數(shù)之和 147

4.5 小結(jié) 148

第 5 章 樹與二叉樹 149

5.1 樹的簡介 149

5.1.1 樹的常用術(shù)語 149

5.1.2 樹的表示方式 151

5.2 二叉樹 152

5.2.2 樹的查找操作 157

5.2.3 樹的刪除操作 158

5.2.4 獲得樹的結(jié)點(diǎn)數(shù) 160

5.2.5 獲得樹的高度 161

5.2.6 樹的深度優(yōu)先遍歷 161

5.2.7 深度優(yōu)先遍歷的遞歸實(shí)現(xiàn) 163

5.2.8 深度優(yōu)先遍歷的非遞歸實(shí)現(xiàn) 167

5.2.9 深度優(yōu)先遍歷的非遞歸實(shí)現(xiàn)的優(yōu)化 173

5.2.10 樹的廣度優(yōu)先遍歷 176

5.2.11 樹的打印 177

5.3 二叉查找樹 186

5.3.1 BST 的插入與查找操作 187

5.3.2 前驅(qū)結(jié)點(diǎn)與后繼結(jié)點(diǎn) 188

5.3.3 BST 的移除操作 190

5.4 總結(jié) 192

第 6 章堆與優(yōu)先隊(duì)列 194

6.1 二叉堆 194

6.2 堆排序 196

6.3 topK 問題 203

6.4 優(yōu)先隊(duì)列 205

6.5 丑數(shù) 208

6.6 小結(jié) 210

第 7 章 并查集 210

7.1 沒有優(yōu)化的并查集 210

7.2 快速合并，慢查找 214

7.3 基于重量的快速合并，快速查找 218

7.4 基于深度的快速合并，快速查找 220

7.5 基于深度與路徑壓縮的快速合并，快速查找 223

7.6 相關(guān)問題 226

7.6.1 朋友圈 226

7.6.2 島嶼的數(shù)量 228

7.6.3 賬戶合并 229

7.6.4 團(tuán)伙問題 232

7.6.5 食物鏈 233

7.7 總結(jié) 235

第 8 章 線段樹 237

8.1 普通線段樹 237

8.1.1 構(gòu)建 237

8.1.2 單點(diǎn)查詢 240

8.1.3 單點(diǎn)修改 240

8.1.4 區(qū)間查詢 242

8.1.5 區(qū)間修改 243

8.1.6 延遲標(biāo)記 244

8.2 ZKW 線段樹 247

8.2.1 構(gòu)建 247

8.2.2 單點(diǎn)查詢 248

8.2.3 單點(diǎn)修改 249

8.2.4 區(qū)間查詢 249

8.3 標(biāo)記永久化技巧 251

8.3.1 基于標(biāo)記永久化的區(qū)間修改 251

8.3.2 基于標(biāo)記永久化的區(qū)間查詢 252

8.4 差分思想 253

8.4.1 基于差分思想的區(qū)間修改 254

8.4.2 基于差分思想的區(qū)間查詢 255

8.5 總結(jié) 255

第 9 章 樹狀數(shù)組 256

9.1 原理 256

9.2 構(gòu)建 262

9.3 單點(diǎn)查詢 263

9.4 單點(diǎn)修改 264

9.5 求前 n 項(xiàng)之和 265

9.6 求 a~b 項(xiàng)之和 266

9.7 區(qū)間更新 266

9.8 區(qū)間最值 266

9.9 求逆序數(shù) 269

9.10 數(shù)組離散化 269

9.11 總結(jié) 273

第 10 章 前綴樹 274

10.1 原理 274

10.2 插入字符串 275

10.3 移除字符串 277

10.4 是否包含某個(gè)字符串 277

10.5 是否包含某個(gè)前綴 278

10.6 統(tǒng)計(jì)某個(gè)字符串出現(xiàn)的次數(shù) 278

10.7 統(tǒng)計(jì)某個(gè)前綴出現(xiàn)的次數(shù) 279

10.8 優(yōu)化 279

10.9 排序 280

10.10 求最長公共前綴 282

10.11 模糊搜索 283

10.12 總結(jié) 284

第 11 章 跳表 286

11.1 跳表的結(jié)構(gòu) 286

11.2 跳表的性質(zhì) 286

11.3 插入 287

11.4 查找 289

11.5 刪除 290

11.6 得到排序數(shù)組 291

11.7 總結(jié) 291

第 12 章 簡單平衡樹 293

12.1 有旋 Treap 293

12.1.1 旋轉(zhuǎn) 294

12.1.2 插入 297

12.1.3 查找 299

12.1.4 刪除 299

12.1.5 各種遍歷 301

12.1.6 獲取 value 的排名 302

12.1.7 根據(jù)排名找對(duì)應(yīng)的數(shù) 302

12.2 無旋 Treap 304

12.2.1 合并 305

12.2.2 拆分 309

12.2.3 添加 313

12.2.4 移除 314

12.2.5 查找 314

12.2.6 獲取 value 的排名 314

12.2.7 根據(jù)排名找對(duì)應(yīng)的數(shù) 315

12.2.8 求前驅(qū)后繼 315

12.2.9 求最大最小值 316

12.3 伸展樹 317

12.3.2 查找 323

12.3.3 插入 323

12.3.4 刪除 325

12.3.5 區(qū)間刪除 326

12.3.6 獲取 value 的排名 327

12.3.7 根據(jù)排名找對(duì)應(yīng)的數(shù) 327

12.3.8 求最大最小值 327

12.3.9 求前驅(qū)后繼 328

12.3.10 合并 328

12.3.11 拆分 328

12.4 SBT 330

12.4.1 插入 332

12.4.2 刪除 334

12.4.3 平衡 335

12.5 替罪羊樹 341

12.5.1 插入 343

12.5.2 重構(gòu) 345

12.5.3 查找 348

12.5.4 刪除 348

第 13 章 字符串算法 350

13.1 匹配算法 350

13.1.1 Brute‐Force 算法 350

13.1.2 KMP 算法 350

13.1.3 多模式匹配算法 361

13.2 回文算法 367

13.2.1 中央擴(kuò)展法 368

13.2.2 馬拉車算法 369

13.2.3 回文自動(dòng)機(jī) 375

13.2.4 后綴自動(dòng)機(jī) 382

13.3 總結(jié) 397

第 14 章 回溯算法 398

14.1 回溯算法的格式 398

14.2 子集問題的相關(guān)例題 400

14.2.1 沒重復(fù)元素的子集問題 400

14.2.2 有重復(fù)元素的子集問題 401

14.2.3 有重復(fù)元素的組合總和 402

14.2.4 無重復(fù)元素的組合總和 403

14.2.5 背包問題 404

14.2.6 裝載問題 405

14.2.7 火柴拼棍擺正方形 406

14.3 排列問題的相關(guān)例題 408

14.3.1 全排列問題 408

14.3.2 素?cái)?shù)環(huán) 409

14.3.3 批作業(yè)調(diào)度問題 411

14.3.4 八皇后問題 413

14.4 總結(jié) 415

第 15 章 動(dòng)態(tài)規(guī)劃 416

15.1 斐波那契數(shù)列 416

15.1.1 暴力法 417

15.1.2 記憶化搜索 417

15.1.3 動(dòng)態(tài)規(guī)劃法 418

15.2 找零錢 419

15.3 最長不下降子序列 421

15.4 最長公共子序列 423

15.5 爬樓梯 426

15.6 背包問題 427

15.7 總結(jié) 428