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

图书标准信息

• 作者 司徒正美 李晓晨
• 出版社 人民邮电出版社
• 出版时间 2023-04
• 版次 1
• ISBN 9787115596154
• 定价 99.80元
• 装帧 平装
• 开本 16开
• 页数 341页
• 字数 491千字

【内容简介】

本书以JavaScript作为演示代码，比较系统地涉及各种数据结构和常见的算法面试题：常见排序算法（如冒泡排序、选择排序、插入排序、希尔排序、归并排序、堆排序、快速排序、计数排序、桶排序、基数排序等）、树的相关算法、字符串算法、回溯算法、动态规划问题等。本书中没有可怕的数学公式与复杂度证明，而是详细列出解题步骤，给出可以套用的算法模板。为了方便记忆，每种算法都会给出多种解，读者只需从中选取适合自己的解即可。
  本书旨在要让非科班出身的、没有算法基础的前端人士能够对各种数据结构及相关算法快速上手、顺利通过面试。

【作者简介】

司徒正美（真名钟钦成）

著名的JavaScript专家，曾在去哪儿网担任前端架构师，立志做考古学家的日语系工程师，穿梭于二次元与二进制间的“魔法师”，做过陶艺，写过小说，涉猎Java、Ruby、JavaScript，常年活跃在开源社区，曾出版《JavaScript框架设计》一书。

李晓晨

资深前端工程师，曾在美团、快手任职，对算法、基础框架、互动技术、DX有一定研究，最近对Web 3产生了浓厚的兴趣。

【目录】

前言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 有旋 Treap293

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 无旋 Treap304

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 SBT330

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