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

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