Labuladong的算法笔记

"在你还没有拿得出手的实战项目证明自己能力时，面试官只能拿算法题评估你。力扣算法题因被BAT、京东、美团、字节跳动、滴滴、微软、亚马逊、Google、Facebook等一线科技公司选作面试题而名声大噪，不论你是想拿下大厂Offer，还是想在技术道路上走得更远，刷算法题，尤其是刷力扣算法题，无疑是一个高效率的选择。 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.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