前言 6
第 1 章 时间复杂度与空间复杂度 10
1.1 时间复杂度 10
1.2 空间复杂度 15
1.3 总结 17
1. 时间复杂度 17
2. 空间复杂度 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 快速排序的优化 52
2.7.3 非递归实现 54
2.7.4 算法比较 55
2.7.5 快速排序的一些应用 55
2.8 计数排序 56
2.9 桶排序 58
2.10 基数排序 61
2.10.1 LSD 基数排序 61
2.10.2 MSD 基数排序 64
2.10.3 字符串使用基数排序实现字典排序 66
2.11 总结 68
2.11.1 算法使用场景 69
第 3 章 线性结构 71
3.1 数据结构的分类 71
3.2 数组 73
3.3 链表 75
3.3.1 单向链表 75
3.3.2 双向链表 78
3.3.3 有序链表 80
3.3.4 循环双向链表 83
3.3.5 链表排序 88
3.4 栈 96
3.4.1 栈的特点和相关概念 96
3.4.2 栈相关的方法 98
3.4.3 栈的应用场景 99
3.5 队列 106
3.5.1 队列的常用方法 107
3.5.2 队列的典型应用 108
3.6 散列简述 109
3.6.1 散列函数 109
3.6.2 散列冲突的解决方案 112
3.6.3 散列的应用 121
3.7 位图 124
3.7.1 位图简述 124
3.7.2 位图的应用 127
3.8 块状链表 129
3.8.1 块状链表简介 129
3.8.2 块状链表的操作 130
3.9 总结 136
第 4 章 散列详谈 139
4.1 散列的定义 139
4.2 常见的散列算法 139
4.3 散列冲突的解决方案 141
4.3.1 开散列方法 142
4.3.2 闭散列方法 144
4.4 散列的应用 146
4.4.1 数组去重 146
4.4.2 求只出现一次的数字 147
4.4.3 两数之和 147
4.5 小结 148
第 5 章 树与二叉树 149
5.1 树的简介 149
5.1.1 树的常用术语 149
5.1.2 树的表示方式 151
5.2 二叉树 152
5.2.2 树的查找操作 157
5.2.3 树的删除操作 158
5.2.4 获得树的结点数 160
5.2.5 获得树的高度 161
5.2.6 树的深度优先遍历 161
5.2.7 深度优先遍历的递归实现 163
5.2.8 深度优先遍历的非递归实现 167
5.2.9 深度优先遍历的非递归实现的优化 173
5.2.10 树的广度优先遍历 176
5.2.11 树的打印 177
5.3 二叉查找树 186
5.3.1 BST 的插入与查找操作 187
5.3.2 前驱结点与后继结点 188
5.3.3 BST 的移除操作 190
5.4 总结 192
第 6 章堆与优先队列 194
6.1 二叉堆 194
6.2 堆排序 196
6.3 topK 问题 203
6.4 优先队列 205
6.5 丑数 208
6.6 小结 210
第 7 章 并查集 210
7.1 没有优化的并查集 210
7.2 快速合并，慢查找 214
7.3 基于重量的快速合并，快速查找 218
7.4 基于深度的快速合并，快速查找 220
7.5 基于深度与路径压缩的快速合并，快速查找 223
7.6 相关问题 226
7.6.1 朋友圈 226
7.6.2 岛屿的数量 228
7.6.3 账户合并 229
7.6.4 团伙问题 232
7.6.5 食物链 233
7.7 总结 235
第 8 章 线段树 237
8.1 普通线段树 237
8.1.1 构建 237
8.1.2 单点查询 240
8.1.3 单点修改 240
8.1.4 区间查询 242
8.1.5 区间修改 243
8.1.6 延迟标记 244
8.2 ZKW 线段树 247
8.2.1 构建 247
8.2.2 单点查询 248
8.2.3 单点修改 249
8.2.4 区间查询 249
8.3 标记永久化技巧 251
8.3.1 基于标记永久化的区间修改 251
8.3.2 基于标记永久化的区间查询 252
8.4 差分思想 253
8.4.1 基于差分思想的区间修改 254
8.4.2 基于差分思想的区间查询 255
8.5 总结 255
第 9 章 树状数组 256
9.1 原理 256
9.2 构建 262
9.3 单点查询 263
9.4 单点修改 264
9.5 求前 n 项之和 265
9.6 求 a~b 项之和 266
9.7 区间更新 266
9.8 区间最值 266
9.9 求逆序数 269
9.10 数组离散化 269
9.11 总结 273
第 10 章 前缀树 274
10.1 原理 274
10.2 插入字符串 275
10.3 移除字符串 277
10.4 是否包含某个字符串 277
10.5 是否包含某个前缀 278
10.6 统计某个字符串出现的次数 278
10.7 统计某个前缀出现的次数 279
10.8 优化 279
10.9 排序 280
10.10 求最长公共前缀 282
10.11 模糊搜索 283
10.12 总结 284
第 11 章 跳表 286
11.1 跳表的结构 286
11.2 跳表的性质 286
11.3 插入 287
11.4 查找 289
11.5 删除 290
11.6 得到排序数组 291
11.7 总结 291
第 12 章 简单平衡树 293
12.1 有旋 Treap 293
12.1.1 旋转 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 根据排名找对应的数 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 根据排名找对应的数 315
12.2.8 求前驱后继 315
12.2.9 求最大最小值 316
12.3 伸展树 317
12.3.2 查找 323
12.3.3 插入 323
12.3.4 删除 325
12.3.5 区间删除 326
12.3.6 获取 value 的排名 327
12.3.7 根据排名找对应的数 327
12.3.8 求最大最小值 327
12.3.9 求前驱后继 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 重构 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 中央扩展法 368
13.2.2 马拉车算法 369
13.2.3 回文自动机 375
13.2.4 后缀自动机 382
13.3 总结 397
第 14 章 回溯算法 398
14.1 回溯算法的格式 398
14.2 子集问题的相关例题 400
14.2.1 没重复元素的子集问题 400
14.2.2 有重复元素的子集问题 401
14.2.3 有重复元素的组合总和 402
14.2.4 无重复元素的组合总和 403
14.2.5 背包问题 404
14.2.6 装载问题 405
14.2.7 火柴拼棍摆正方形 406
14.3 排列问题的相关例题 408
14.3.1 全排列问题 408
14.3.2 素数环 409
14.3.3 批作业调度问题 411
14.3.4 八皇后问题 413
14.4 总结 415
第 15 章 动态规划 416
15.1 斐波那契数列 416
15.1.1 暴力法 417
15.1.2 记忆化搜索 417
15.1.3 动态规划法 418
15.2 找零钱 419
15.3 最长不下降子序列 421
15.4 最长公共子序列 423
15.5 爬楼梯 426
15.6 背包问题 427
15.7 总结 428
鄂公网安备 42010302001612号 