labuladong的算法笔记

图书标准信息

• 作者 付东来（@labuladong）
• 出版社 电子工业出版社
• 出版时间 2023-08
• 版次 1
• ISBN 9787121457821
• 定价 119.00元
• 装帧 其他
• 开本 16开
• 页数 516页
• 字数 0.7千字

【内容简介】

本书专攻算法刷题，训练算法思维，应对算法笔试，注重用套路和框架思维解决问题，以不变应万变。第1章列举了几个最常见的算法类型及对应的解题框架思路，包括双指针、滑动窗口等算法技巧，并把动态规划、回溯算法、广度优先搜索等技巧的核心抽象为二叉树的两种问题形式。第2章介绍了基础数据结构相关的算法，包括数组链表的常见技巧汇总和数据结构设计的经典例题。第3章从二叉树的几种解题思路开始，尝试从二叉树的视角理解快速排序和归并排序，进一步讲解回溯、DFS、BFS等暴力搜索算法。第4章具体介绍了动态规划相关的技巧，例如如何确定base case，如何写状态转移方程，如何进行状态压缩等技巧，并用动态规划的通用思路框架解决了十几道经典的动态规划问题。第5章讲解了一些高频面试/笔试题目，每道题目可能会结合之前章节讲过的多种算法思路，也可能有多种解法。读完这一章，你就可以独自遨游题海啦！

【作者简介】

付东来（@labuladong为其网名），微信公众号labuladong的作者，有多年的刷题经验，希望用通俗的语言帮助广大互联网从业者少走弯路，快速从根本上攻克算法难关，为职业道路的发展赋能。

【目录】

本书约定/1

编程语言基础/4

章核心框架篇/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.2n皇后问题52

1.4.3后结55

1.5bfs算法解题套路框架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.2union-find算法详解245

3.3.3小生成树之kruskal算法259

3.4暴力搜索算法268

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

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

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

3.4.4bfs算法解决智力游戏317

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

4.1动态规划核心323

4.1.1basecase和备忘录的初始值怎么定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.10-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.1twosum问题483

5.7.23sum问题486

5.7.34sum问题488

5.7.4100sum问题489

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

5.8.1寻找一个元素492

5.8.2解决五道题目495