labuladong的算法笔记

本书专攻算法刷题，训练算法思维，应对算法笔试，注重用套路和框架思维解决问题，以不变应万变。

第1章列举了几个最常见的算法类型及对应的解题框架思路，包括双指针、滑动窗口等算法技巧，并把动态规划、回溯算法、广度优先搜索等技巧的核心抽象为二叉树的两种问题形式。

第2章介绍了基础数据结构相关的算法，包括数组链表的常见技巧汇总和数据结构设计的经典例题。

第3章从二叉树的几种解题思路开始，尝试从二叉树的视角理解快速排序和归并排序，进一步讲解回溯、DFS、BFS等暴力搜索算法。

第4章具体介绍了动态规划相关的技巧，例如如何确定base case，如何写状态转移方程，如何进行状态压缩等技巧，并用动态规划的通用思路框架解决了十几道经典的动态规划问题。

第5章讲解了一些高频面试/笔试题目，每道题目可能会结合之前章节讲过的多种算法思路，也可能有多种解法。读完这一章，你就可以独自遨游题海啦！

labuladong，有多年的刷题经验，希望用通俗的语言帮助广大互联网从业者少走弯路，快速从根本上攻克算法难关，为职业道路的发展赋能。

这不是一本数据结构和算法的入门书，而是一本刷算法题的参考书。

算法原理+力扣原题实战，理论与实践并重。

刷题并不是目的，形成属于自己的解题方法论才是目的。
从树的视角理解所有「烧脑」的递归算法，解锁不一样的思维模式。
洞悉题目的内在联系，任它千般变化，你也能直指核心，沉稳应对。
几百张手绘算法原理图，几十个可视化面板展示算法过程，降低理解成本，加强学习效果。

数据结构和算法在计算机知识体系中有着举足轻重的作用，这块知识也有非常经典的教材供我们学习。但是，我们刷的算法题往往会在经典的算法思想之上套层皮，所以很容易让人产生这种感觉：我以前的数据结构和算法学得挺好的，为什么这些算法题我完全没思路呢？

面对这种疑惑，可能就会有人摆出好几本算法相关的大部头，建议你去进修。

有些书确实很经典，但我觉得咱们应该搞清楚自己的目的是什么。如果你是学生，对算法有浓厚的兴趣，甚至说以后准备搞这方面的研究，那我觉得你可以去啃一啃大部头；但事实是，大部分人学习算法是为了应对考试，这种情况去啃大部头的性价比就比较低了，更高效的方法是直接刷题。

但是，刷题也是有技巧的，刷题平台动辄几千道题，难道你全刷完吗？最高效的刷题方式是边刷边归纳总结，抽象出每种题型的套路框架，以不变应万变。我个人还是挺喜欢刷题的，经过长时间的积累总结，沉淀出了这本书，希望能给你带来思路上的启发和指导。

解算法题的核心只有一个，那就是穷举。不同的算法，无非就是聪明的穷举和笨一点儿的穷举而已，真的没什么高深莫测的，读完本书，你就会有深刻的体会。

本书约定 / 1

编程语言基础 / 4

第1章 核心框架篇 / 15

1.1 学习数据结构和算法的框架思维 15

1.1.1 数据结构的存储方式 16

1.1.2 数据结构的基本操作 17

1.1.3 算法刷题指南 18

1.2 计算机算法的本质 24

1.2.1 算法的本质 24

1.2.2 数组/ 单链表系列算法 26

1.2.3 二叉树系列算法 28

1.2.4 最后总结 33

1.3 动态规划解题套路框架 33

1.3.1 斐波那契数列 35

1.3.2 凑零钱问题 40

1.3.3 最后总结 45

1.4 回溯算法解题套路框架 46

1.4.1 全排列问题 47

1.4.2 N皇后问题 52

1.4.3 最后总结 55

1.5 BFS算法解题套路框架 55

1.5.1 算法框架 56

1.5.2 二叉树的最小高度 57

1.5.3 解开密码锁的最少次数 59

1.5.4 双向BFS 优化 62

1.6 手把手带你刷二叉树（纲领） 65

1.6.1 二叉树的重要性 66

1.6.2 深入理解前、中、后序 67

1.6.3 两种解题思路 71

1.6.4 后序位置的特殊之处 75

1.6.5 层序遍历 79

1.7 我写了首诗，保你闭着眼睛都能写出二分搜索算法 81

1.7.1 二分搜索框架 82

1.7.2 寻找一个数（基本的二分搜索） 82

1.7.3 寻找左侧边界的二分搜索 84

1.7.4 寻找右侧边界的二分搜索 88

1.7.5 逻辑统一 90

1.8 我写了一个模板，把滑动窗口算法变成了默写题 93

1.8.1 最小覆盖子串 96

1.8.2 字符串排列 100

1.8.3 找所有字母异位词 102

1.8.4 最长无重复子串 103

第2章 手把手刷数据结构 / 105

2.1 数组、链表 105

2.1.1 单链表的六大解题套路 105

2.1.2 数组双指针的解题套路 116

2.1.3 小而美的算法技巧：前缀和数组 124

2.1.4 小而美的算法技巧：差分数组 128

2.2 数据结构设计 134

2.2.1 算法就像搭乐高：带你手写LRU算法 135

2.2.2 算法就像搭乐高：带你手写LFU算法 144

2.2.3 以O(1) 时间复杂度删除/ 查找数组中的任意元素 151

2.2.4 单调栈结构解决三道算法题 159

2.2.5 单调队列结构解决滑动窗口问题 164

第3章 手把手培养算法思维 / 170

3.1 二叉树 170

3.1.1 手把手带你刷二叉树（思路） 170

3.1.2 手把手带你刷二叉树（构造） 179

3.1.3 手把手带你刷二叉树（序列化） 192

3.1.3 零、前/ 中/ 后序和二叉树的唯一性 193

3.1.4 归并排序详解及运用 206

3.2 二叉搜索树 215

3.2.1 手把手带你刷二叉搜索树（特性应用） 215

3.2.2 手把手带你刷二叉搜索树（增删查改） 220

3.2.3 快速排序详解及运用 227

3.3 图论算法 237

3.3.1 图论算法基础 237

3.3.2 Union-Find算法详解 245

3.3.3 最小生成树之 Kruskal算法 259

3.4 暴力搜索算法 268

3.4.1 回溯算法解决子集、排列、组合问题 268

3.4.2 经典回溯算法：集合划分问题 291

3.4.3 DFS算法搞定岛屿系列题目 305

3.4.4 BFS算法解决智力游戏 317

第4章 手把手刷动态规划 / 323

4.1 动态规划核心原理 323

4.1.1 base case 和备忘录的初始值怎么定 323

4.1.2 最优子结构和dp 数组的遍历方向怎么定 329

4.1.3 算法时空复杂度分析实用指南 338

4.1.4 动态规划的降维打击：空间压缩技巧 351

4.2 子序列类型问题 358

4.2.1 动态规划设计：最长递增子序列 358

4.2.2 详解最大子数组和 367

4.2.3 详解编辑距离问题 372

4.2.4 详解最长公共子序列问题 381

4.2.5 详解正则匹配问题 389

4.2.6 子序列问题解题模板 397

4.3 背包问题 404

4.3.1 0-1 背包问题解题框架 404

4.3.2 背包问题变体之子集分割 407

4.3.3 背包问题之零钱兑换 410

4.4 用动态规划玩游戏 414

4.4.1 最小路径和问题 414

4.4.2 动态规划算法通关《魔塔》 419

4.4.3 高楼扔鸡蛋问题 426

4.4.4 戳气球问题 438

第5章 高频面试系列 / 445

5.1 链表操作的递归思维一览 445

5.1.1 递归反转整个链表 446

5.1.2 反转链表前N 个节点 448

5.1.3 反转链表的一部分 449

5.2 田忌赛马背后的算法决策 450

5.3 一道数组去重的算法题把我整蒙了 454

5.4 带权重的随机选择算法 458

5.4.1 解法思路 459

5.4.2 解法代码 460

5.5 二分搜索题型套路分析 462

5.5.1 原始的二分搜索代码 463

5.5.2 二分搜索问题的泛化 465

5.5.3 运用二分搜索的套路框架 467

5.5.4 例题一：珂珂吃香蕉 468

5.5.5 例题二：运送货物 471

5.5.6 例题三：分割数组 474

5.6 如何高效解决接雨水问题 475

5.6.1 核心思路 476

5.6.2 备忘录优化 478

5.6.3 双指针解法 479

5.6.4 扩展延伸 481

5.7 一个函数解决nSum 问题 483

5.7.1 twoSum 问题 483

5.7.2 3Sum 问题 486

5.7.3 4Sum 问题 488

5.7.4 100Sum 问题 489

5.8 一个方法解决最近公共祖先问题 491

5.8.1 寻找一个元素 492

5.8.2 解决五道题目 495