Labuladong的算法小抄pdf

Labuladong的算法小抄 作者：付东来（@labuladong）

Labuladong的算法小抄 出版社：电子工业出版社

Labuladong的算法小抄 内容简介

《labuladong的算法小抄》专攻算法刷题，训练算法思维，应对算法笔试。注重用套路和框架思维解决问题，以不变应万变。
第1章列举了几个最常见的算法类型及对应的解题框架思路，包括动态规划、回溯、广度优先搜索及双指针、滑动窗口等算法技巧。

第2章用动态规划的通用思路框架解决了十几道经典的动态规划问题，例如，正则表达式、背包问题，同时还介绍了如何写状态转移方程、如何进行状态压缩等技巧。

第3章介绍了数据结构相关的算法，例如，二叉树相关题目的解法，也包括LRU、LFU这种面试常考的算法原理。

第4章介绍了回溯算法、广度优先搜索算法等核心套路在算法题中的运用，巩固对算法框架的理解。

第5章讲解了一些高频题目，每道题目可能会结合多种算法思路进行讲解，也可能有多种解法，读完这一章，你就可以独自遨游题海啦！

Labuladong的算法小抄 目录

力扣官网题号及名称 /V

本书约定　　／ 1

语言基础　　／ 5

第1章 核心套路篇 ／ 21

1.1 学习算法和刷题的框架思维 ／ 21

1.1.1 数据结构的存储方式 ／ 21

1.1.2 数据结构的基本操作 ／ 23

1.1.3 算法刷题指南 ／ 25

1.1.4 最后总结 ／ 30

1.2 动态规划解题套路框架 ／ 31

1.2.1 斐波那契数列 ／ 32

1.2.2 凑零钱问题 ／ 37

1.2.3 最后总结 ／ 42

1.3 回溯算法解题套路框架 ／ 43

1.3.1 全排列问题 ／ 43

1.3.2 N 皇后问题 ／ 48

1.3.3 最后总结 ／ 51

1.4 BFS 算法套路框架 ／ 53

1.4.1 算法框架 ／ 53

1.4.2 二叉树的最小高度 ／ 54

1.4.3 解开密码锁的最少次数 ／ 56

1.5 双指针技巧套路框架 ／ 64

1.5.1 快、慢指针的常用算法 ／ 64

1.5.2 左、右指针的常用算法 ／ 68

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

1.6.1 二分搜索框架 ／ 72

1.6.2 寻找一个数（基本的二分搜索） ／ 73

1.6.3 寻找左侧边界的二分搜索 ／ 75

1.6.4 寻找右侧边界的二分搜索 ／ 79

1.6.5 逻辑统一 ／ 82

1.7 我写了一个模板，把滑动窗口算法变成了默写题 ／ 85

1.7.1 最小覆盖子串 ／ 87

1.7.2 字符串排列 ／ 91

1.7.3 找所有字母异位词 ／ 93

1.7.4 最长无重复子串 ／ 94

第2章 动态规划系列 ／ 96

2.1 动态规划设计：最长递增子序列 ／ 96

2.1.1 动态规划解法 ／ 97

2.1.2 二分搜索解法 ／ 100

2.2 二维递增子序列：信封嵌套问题 ／ 104

2.2.1 题目概述 ／ 104

2.2.2 思路分析 ／ 105

2.2.3 最后总结 ／ 107

2.3 最大子数组问题 ／ 108

2.3.1 思路分析 ／ 108

2.3.2 最后总结 ／ 110

2.4 动态规划答疑：最优子结构及dp 遍历方向 ／ 111

2.4.1 最优子结构详解 ／ 111

2.4.2 dp 数组的遍历方向 ／ 113

2.5 经典动态规划：最长公共子序列 ／ 117

2.6 经典动态规划：编辑距离 ／ 123

2.6.1 思路分析 ／ 124

2.6.2 代码详解 ／ 125

2.6.3 动态规划优化 ／ 129

2.6.4 扩展延伸 ／ 131

2.7 子序列问题解题模板：最长回文子序列 ／ 136

2.7.1 两种思路 ／ 136

2.7.2 最长回文子序列 ／ 137

2.7.3 代码实现 ／ 139

2.8 状态压缩：对动态规划进行降维打击 ／ 141

2.9 以最小插入次数构造回文串 ／ 148

2.9.1 思路分析 ／ 148

2.9.2 状态转移方程 ／ 149

2.9.3 代码实现 ／ 152

2.10 动态规划之正则表达式 ／ 155

2.10.1 思路分析 ／ 155

2.10.2 动态规划解法 ／ 157

2.11 不同的定义产生不同的解法 ／ 162

2.11.1 第一种思路 ／ 162

2.11.2 第二种思路 ／ 165

2.11.3 最后总结 ／ 167

2.12 经典动态规划：高楼扔鸡蛋 ／ 168

2.12.1 解析题目 ／ 168

2.12.2 思路分析 ／ 169

2.12.3 疑难解答 ／ 172

2.13 经典动态规划：高楼扔鸡蛋（进阶） ／ 173

2.13.1 二分搜索优化 ／ 173

2.13.2 重新定义状态转移 ／ 176

2.13.3 还可以再优化 ／ 180

2.14 经典动态规划：戳气球问题 ／ 181

2.14.1 回溯思路 ／ 181

2.14.2 动态规划思路 ／ 182

2.14.3 写出代码 ／ 185

2.15 经典动态规划：0-1 背包问题 ／ 188

2.16 经典动态规划：子集背包问题 ／ 192

2.16.1 问题分析 ／ 192

2.16.2 思路分析 ／ 193

2.16.3 进行状态压缩 ／ 194

2.17 经典动态规划：完全背包问题 ／ 196

2.18 题目千百变，套路不会变 ／ 200

2.18.1 线性排列情况 ／ 200

2.18.2 环形排列情况 ／ 203

2.18.3 树形排列情况 ／ 205

2.19 动态规划和回溯算法，到底是什么关系 ／ 207

2.19.1 回溯思路 ／ 207

2.19.2 消除重叠子问题 ／ 210

2.19.3 动态规划 ／ 211

第3章 数据结构系列 ／ 216

3.1 手把手教你写 LRU 缓存淘汰算法 ／ 216

3.1.1 LRU 算法描述 ／ 218

3.1.2 LRU 算法设计 ／ 219

3.1.3 代码实现 ／ 220

3.2 层层拆解，带你手写LFU 算法 ／ 227

3.2.1 算法描述 ／ 227

3.2.2 思路分析 ／ 228

3.2.3 代码框架 ／ 230

3.2.4 LFU 核心逻辑 ／ 232

3.3 二叉搜索树操作集锦 ／ 235

3.3.1 判断 BST 的合法性 ／ 236

3.3.2 在 BST 中查找一个数是否存在 ／ 238

3.3.3 在 BST 中插入一个数 ／ 239

3.3.4 在 BST 中删除一个数 ／ 239

3.4 完全二叉树的节点数为什么那么难算 ／ 243

3.4.1 思路分析 ／ 244

3.4.2 复杂度分析 ／ 245

3.5 用各种遍历框架序列化和反序列化二叉树 ／ 247

3.5.1 题目描述 ／ 247

3.5.2 前序遍历解法 ／ 248

3.5.3 后序遍历解法 ／ 252

3.5.4 中序遍历解法 ／ 255

3.5.5 层级遍历解法 ／ 255

3.6 Git 原理之二叉树最近公共祖先 ／ 260

3.6.1 二叉树的最近公共祖先 ／ 261

3.6.2 思路分析 ／ 263

3.7 特殊数据结构：单调栈 ／ 266

3.7.1 单调栈解题模板 ／ 266

3.7.2 题目变形 ／ 268

3.7.3 如何处理循环数组 ／ 268

3.8 特殊数据结构：单调队列 ／ 271

3.8.1 搭建解题框架 ／ 271

3.8.2 实现单调队列数据结构 ／ 273

3.8.3 算法复杂度分析 ／ 276

3.9 如何判断回文链表 ／ 277

3.9.1 判断回文单链表 ／ 277

3.9.2 优化空间复杂度 ／ 280

3.9.3 最后总结 ／ 282

3.10 秀操作之纯递归反转链表 ／ 283

3.10.1 递归反转整个链表 ／ 283

3.10.2 反转链表前N 个节点 ／ 286

3.10.3 反转链表的一部分 ／ 287

3.10.4 最后总结 ／ 288

3.11 秀操作之k 个一组反转链表 ／ 289

3.11.1 分析问题 ／ 289

3.11.2 代码实现 ／ 291

3.11.3 最后总结 ／ 292

第4章 算法思维系列 ／ 293

4.1 回溯算法解决子集、组合、排列问题 ／ 293

4.1.1 子集 ／ 293

4.1.2 组合 ／ 297

4.1.3 排列 ／ 299

4.2 回溯算法最佳实践：解数独 ／ 301

4.2.1 直观感受 ／ 301

4.2.2 代码实现 ／ 301

4.3 回溯算法最佳实践：括号生成 ／ 306

4.4 BFS 算法暴力破解各种智力题 ／ 310

4.4.1 题目解析 ／ 311

4.4.2 思路分析 ／ 311

4.5 2Sum 问题的核心思想 ／ 315

4.5.1 2Sum I ／ 315

4.5.2 2Sum II ／ 316

4.5.3 最后总结 ／ 318

4.6 一个函数解决 nSum 问题 ／ 319

4.6.1 2Sum 问题 ／ 319

4.6.2 3Sum 问题 ／ 322

4.6.3 4Sum 问题 ／ 324

4.6.4 100Sum 问题 ／ 325

4.7 拆解复杂问题：实现计算器 ／ 328

4.7.1 字符串转整数 ／ 328

4.7.2 处理加减法 ／ 329

4.7.3 处理乘除法 ／ 331

4.7.4 处理括号 ／ 333

4.7.5 最后总结 ／ 336

4.8 摊烧饼也得有点递归思维 ／ 337

4.8.1 思路分析 ／ 338

4.8.2 代码实现 ／ 339

4.9 前缀和技巧解决子数组问题 ／ 341

4.9.1 什么是前缀和 ／ 341

4.9.2 优化解法 ／ 343

4.9.3 最后总结 ／ 344

4.10 扁平化嵌套列表 ／ 345

4.10.1 题目描述 ／ 345

4.10.2 解题思路 ／ 346

4.10.3 进阶思路 ／ 349

第5章 高频面试系列 ／ 351

5.1 如何高效寻找素数 ／ 351

5.2 如何高效进行模幂运算 ／ 355

5.2.1 如何处理数组指数 ／ 355

5.2.2 如何处理 mod 运算 ／ 356

5.2.3 如何高效求幂 ／ 358

5.3 如何运用二分搜索算法 ／ 360

5.3.1 问题分析 ／ 360

5.3.2 扩展延伸 ／ 362

5.4 如何高效解决接雨水问题 ／ 364

5.5 如何去除有序数组的重复元素 ／ 371

5.6 如何寻找最长回文子串 ／ 373

5.7 如何运用贪心思想玩跳跃游戏 ／ 376

5.8 如何运用贪心算法做时间管理 ／ 381

5.9 如何判定括号合法性 ／ 386

5.10 如何调度考生的座位 ／ 389

5.11 Union-Find 算法详解 ／ 396