内容简介

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

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

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

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

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

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

作品目录

本书约定 / 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 解决五道题目 49
· · · · · ·

作者简介

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