JavaScript算法：基本原理与代码实现

司徒正美（真名钟钦成）
著名的JavaScript专家，曾在去哪儿网担任前端架构师，立志做考古学家的日语系工程师，穿梭于二次元与二进制间的“魔法师”，做过陶艺，写过小说，涉猎Java、Ruby、JavaScript，常年活跃在开源社区，曾出版《JavaScript框架设计》一书。
李晓晨
资深前端工程师，曾在美团、快手任职，对算法、基础框架、互动技术、DX有一定研究，最近对Web 3产生了浓厚的兴趣。

适读人群 ：初中级的前端开发人员

1.由JavaScript魔术师司徒正美和快手前端开发人员李晓晨合作撰写，具备全面的理论知识和丰富的实践经验，前端大神司徒正美撰写的最后一本作品。
2.采用JavaScript作为演示代码，比较系统地涉及各种数据结构和常见的算法面试题，内容丰富可靠。
3.书中没有数学公式和复杂度证明，而是详细列出解题步骤，给出可以套用的算法模板，非科班出身的读者也能轻松上手。
4.涵盖了常见排序算法、树的相关算法、字符串算法、回溯算法、动态规划问题等多个领域，是一本实用的算法入门指南。
5.以简单易懂的语言讲解算法原理，同时配有代码实现，让读者能够深入理解和掌握各种算法，并成功通过前端面试。
6.快手研发总监方超、《深入浅出Vue.js》作者刘博文（玖五）、《TypeScript入门实战笔记》作者乾元、独立开发者&讲师花果山大圣联袂推荐

前言 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