Hello 算法
C++ 语言版
靳宇栋（Krahets）
Release 1.0.0b4
2023‑07‑26
序
两年前，我在力扣上分享了《剑指 Oer》系列题解，受到了许多朋友的喜爱与支持。在此期间，我回答了众
多读者的评论问题，其中最常见的一个问题是“如何入门学习算法”。我逐渐也对这个问题产生了浓厚的兴
趣。
两眼一抹黑地刷题似乎是最受欢迎的方法，简单直接且有效。然而，刷题就如同玩“扫雷”游戏，自学能力
强的同学能够顺利地将地雷逐个排掉，而基础不足的同学很可能被炸的满头是包，并在挫折中步步退缩。通
读教材书籍也是一种常见做法，但对于面向求职的同学来说，毕业季、投递简历、准备笔试面试已经占据了
大部分精力，厚重的书籍往往变成了一项艰巨的挑战。
如果你也面临类似的困扰，那么很幸运这本书找到了你。本书是我对此问题的给出的答案，虽然不一定正确，
但至少是一次积极的尝试。这本书虽然不足以让你直接拿到 Oer ，但会引导你探索数据结构与算法的“知
识地图”，带你了解不同“地雷”的形状大小和分布位置，让你掌握各种“排雷方法”。有了这些本领，相信
你可以更加自如地应对刷题和阅读文献，逐步构建起完整的知识体系。
本书中的代码附有可一键运行的源文件，托管于 github.com/krahets/hello‑algo 仓库。动画在 PDF 内的
展示效果受限，可访问 hello‑algo.com 网页版以获得更优的阅读体验。
致谢
本书在开源社区众多贡献者的共同努力下不断成长。感谢每一位投入 时 间 与 精 力 的 撰 稿 人， 他 们
是（按照 GitHub 自动生成的顺序）：krahets, sjinzh, justin‑tse, Reanon, nuomi1, Gonglja, S‑N‑O‑
R‑L‑A‑X, danielsss, hpstory, RiverTwilight, msk397, gyt95, zhuoqinyue, FangYuan33, mingXta,
gvenusleo, Xia‑Sang, night‑cruise, guowei‑gong, GN‑Yu, xBLACKICEx, JoseHung, IsChristina,
pengchzn, qualier1024, Guanngxu, Cathay‑Chen, what‑is‑me, L‑Super, Slone123c, mgisr,
WSL0809, longsizhuo, JeersonHuang, longranger2, xiongsp, hongyun‑robot, Wonderdch, a16su,
NI‑SW, xjr7670, MolDuM, XC‑Zero, DullSword, iron‑irax, yuan0221, wangwang105, ZongYangL,
shanghai‑Jerry, curly210102, Suremotoo, linzeyan, yi427, boloboloda, huawuque404, 4yDX3906,
ZJKung, xb534, siqyka, ZnYang2018, beintentional, luluxia, GaochaoZhu, weibk, dshlstarr,
ShiMaRing, fbigm, dyizheng, iStig, YuelinXin, szu17dmy, hezhizhen, fanchenggang, Keynman,
youshaoXG, lipusheng, Javesun99, tao363, czruby, gltianwen, liuxjerry, yabo083.
本书的代码审阅工作由 Gonglja, gvenusleo, hpstory, justin‐tse, krahets, nuomi1, Reanon, sjinzh 完
成（按照首字母顺序排列）。感谢他们付出的时间与精力，正是他们确保了各语言代码的规范与统一。
推荐语
“一本通俗易懂的数据结构与算法入门书，引导读者手脑并用地学习，强烈推荐算法初学者阅读。”
——邓俊辉，清华大学计算机系教授
“如果我当年学数据结构与算法的时候有《Hello 算法》，学起来应该会简单 10 倍！”
——李沐，亚马逊资深首席科学家
i
目 录
0. 前言 1
0.1. 关于本书 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
0.2. 如何使用本书 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
0.3. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1. 初识算法 7
1.1. 算法无处不在 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2. 算法是什么 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2. 复杂度 13
2.1. 算法效率评估 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2. 时间复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3. 空间复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3. 数据结构 37
3.1. 数据结构分类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2. 基本数据类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3. 数字编码 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4. 字符编码 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.5. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4. 数组与链表 50
4.1. 数组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2. 链表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3. 列表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.4. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5. 栈与队列 68
5.1. 栈 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.2. 队列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.3. 双向队列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.4. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
6. 散列表 92
6.1. 哈希表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
6.2. 哈希冲突 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.3. 哈希算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6.4. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
7. 树 113
7.1. 二叉树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
7.2. 二叉树遍历 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
7.3. 二叉树数组表示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
7.4. 二叉搜索树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
7.5. AVL 树 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
7.6. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
8. 堆 149
8.1. 堆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
目 录 hello‑algo.com ii
8.2. 建堆操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
8.3. Top‑K 问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
8.4. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
9. 图 163
9.1. 图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
9.2. 图基础操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
9.3. 图的遍历 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
9.4. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
10. 搜索 182
10.1. 二分查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
10.2. 二分查找边界 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
10.3. 哈希优化策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
10.4. 重识搜索算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
10.5. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
11. 排序 195
11.1. 排序算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
11.2. 选择排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
11.3. 冒泡排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
11.4. 插入排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
11.5. 快速排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
11.6. 归并排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
11.7. 堆排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
11.8. 桶排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
11.9. 计数排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
11.10. 基数排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
11.11. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
12. 分治 229
12.1. 分治算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
12.2. 分治搜索策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
12.3. 构建二叉树问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
12.4. 汉诺塔问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
12.5. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
13. 回溯 245
13.1. 回溯算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
13.2. 全排列问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
13.3. 子集和问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
13.4. N 皇后问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
13.5. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
14. 动态规划 271
14.1. 初探动态规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
14.2. 动态规划问题特性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
14.3. 动态规划解题思路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
14.4. 0‑1 背包问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
14.5. 完全背包问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
14.6. 编辑距离问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
14.7. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
15. 贪心 317
15.1. 贪心算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
15.2. 分数背包问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
