Hello 算法
TypeScript 语言版
靳宇栋（Krahets）
Release 1.0.0b5
2023‑09‑10
序
两年前，我在力扣上分享了《剑指 Oer》系列题解，受到了许多同学的喜爱和支持。在与读者的交流期间，
最常收到的一个问题是“如何入门学习算法”。我逐渐对这个问题产生了浓厚的兴趣。
两眼一抹黑地刷题似乎是最受欢迎的方法，简单直接且有效。刷题就如同玩“扫雷”游戏，自学能力强的同
学能够顺利地将地雷逐个排掉，而基础不足的同学很可能被炸的满头是包，并在挫折中步步退缩。通读教材
书籍也是一种常见做法，但对于面向求职的同学来说，毕业季、投递简历、准备笔试面试已经占据了大部分
精力，厚重的书籍往往变成了一项艰巨的挑战。
如果你也面临类似的困扰，那么很幸运这本书找到了你。本书是我对此问题的给出的答案，即使不是最优解，
也至少是一次积极的尝试。这本书虽然不足以让你直接拿到 Oer ，但会引导你探索数据结构与算法的“知
识地图”，带你了解不同“地雷”的形状大小和分布位置，让你掌握各种“排雷方法”。有了这些本领，相信
你可以更加自如地应对刷题和阅读文献，逐步构建起完整的知识体系。
本书中的代码附有可一键运行的源文件，托管于 github.com/krahets/hello‑algo 仓库。动画在 PDF 内的
展示效果受限，可访问 hello‑algo.com 网页版以获得更优的阅读体验。
推荐语
“一本通俗易懂的数据结构与算法入门书，引导读者手脑并用地学习，强烈推荐算法初学者阅读。”
——邓俊辉，清华大学计算机系教授
“如果我当年学数据结构与算法的时候有《Hello 算法》，学起来应该会简单 10 倍！”
——李沐，亚马逊资深首席科学家
致谢
本书在开源社区众多贡献者的共同努力下不断成长。感谢每一位投入时间与精力的撰稿人，他们是
（按照 GitHub 自动 生成 的顺 序）：krahets, justin‑tse, sjinzh, nuomi1, Reanon, Gonglja, S‑N‑O‑R‑
L‑A‑X, hpstory, danielsss, RiverTwilight, gvenusleo, msk397, gyt95, night‑cruise, zhuoqinyue,
FangYuan33, mingXta, Xia‑Sang, guowei‑gong, GN‑Yu, xBLACKICEx, JoseHung, IsChristina,
pengchzn, qualier1024, Guanngxu, Cathay‑Chen, longsizhuo, yuan0221, WSL0809, what‑is‑
me, L‑Super, Slone123c, mgisr, JeersonHuang, longranger2, xiongsp, gaofer, hongyun‑robot,
Wonderdch, a16su, XiaChuerwu, yd‑j, NI‑SW, xjr7670, MolDuM, XC‑Zero, DullSword, iron‑irax,
lwbaptx, baa‑god, Richard‑Zhang1019, psychelzh, ElaBosak233, bubble9um, yishangzhang,
wangwang105, ZongYangL, shanghai‑Jerry, curly210102, Suremotoo, linzeyan, yi427, boloboloda,
huawuque404, 4yDX3906, ZJKung, xb534, siqyka, ZnYang2018, beintentional, luluxia, GaochaoZhu,
weibk, dshlstarr, ShiMaRing, fbigm, chadyi, iStig, yuelinxin, szu17dmy, hezhizhen, fanchenggang,
Keynman, youshaoXG, lipusheng, Javesun99, tao363, czruby, gltianwen, liuxjerry, yabo083.
本书的代码审阅工作由 Gonglja, gvenusleo, hpstory, justin‐tse, krahets, nuomi1, Reanon, sjinzh 完
成（按照首字母顺序排列）。感谢他们付出的时间与精力，正是他们确保了各语言代码的规范与统一。
i
目 录
第 0 章 前言 1
0.1 关于本书 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
0.2 如何使用本书 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
0.3 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
第 1 章 初识算法 9
1.1 算法无处不在 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2 算法是什么 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
第 2 章 复杂度分析 16
2.1 算法效率评估 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 迭代与递归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 时间复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4 空间复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
第 3 章 数据结构 48
3.1 数据结构分类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2 基本数据类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.3 数字编码 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4 字符编码 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
第 4 章 数组与链表 62
4.1 数组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2 链表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.3 列表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.4 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
第 5 章 栈与队列 83
5.1 栈 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.2 队列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.3 双向队列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.4 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
第 6 章 哈希表 107
6.1 哈希表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.2 哈希冲突 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.3 哈希算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
6.4 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
第 7 章 树 129
7.1 二叉树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.2 二叉树遍历 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
7.3 二叉树数组表示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
7.4 二叉搜索树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
7.5 AVL 树 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
7.6 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
目 录 hello‑algo.com ii
第 8 章 堆 167
8.1 堆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
8.2 建堆操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
8.3 Top‑K 问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
8.4 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
第 9 章 图 182
9.1 图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
9.2 图基础操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
9.3 图的遍历 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
9.4 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
第 10 章 搜索 202
10.1 二分查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
10.2 二分查找插入点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
10.3 二分查找边界 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
10.4 哈希优化策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
10.5 重识搜索算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
10.6 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
第 11 章 排序 220
11.1 排序算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
11.2 选择排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
11.3 冒泡排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
11.4 插入排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
11.5 快速排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
11.6 归并排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
11.7 堆排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
11.8 桶排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
11.9 计数排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
11.10 基数排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
11.11 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
第 12 章 分治 256
12.1 分治算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
12.2 分治搜索策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
12.3 构建二叉树问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
12.4 汉诺塔问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
12.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
第 13 章 回溯 273
13.1 回溯算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
13.2 全排列问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
13.3 子集和问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
13.4 N 皇后问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
13.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
第 14 章 动态规划 302
14.1 初探动态规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
14.2 动态规划问题特性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
14.3 动态规划解题思路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
14.4 0‑1 背包问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
14.5 完全背包问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
14.6 编辑距离问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
14.7 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
