原创 labuladong labuladong 今天
labuladong
推荐搜索
关键词列表：学习指南二叉树动态规划详解图论
两年前刚开这个公众号的时候，我写了一篇 学习数据结构和算法的框架思维，现在已经 5w 多阅读了，这对于一篇纯技术文来说是很牛逼的数据。+
这两年在我自己不断刷题，思考和写公众号的过程中，我对算法的理解也是在逐渐加深，所以今天再写一篇，把我这两年的经验和思考浓缩成 4000 字，分享给大家。
本文主要有两部分，一是谈我对算法本质的理解，二是概括各种常用的算法。全文没有什么硬核的代码，都是我的经验之谈，也许没有多么高大上，但肯定能帮你少走弯路，更透彻地理解和掌握算法。
另外，本文包含大量历史文章链接，结合本文阅读历史文章也许可以更快培养出学习算法的框架思维和知识体系。
算法的本质
如果要让我一句话总结，我想说算法的本质就是「穷举」。
这么说肯定有人要反驳了，真的所有算法问题的本质都是穷举吗？没有一个例外吗？
例外肯定是有的，比如前几天我还发了 一行代码就能解决的算法题，这些题目都是通过观察，发现规律，然后找到最优解法。
再比如数学相关的算法，很多都是数学推论，然后用编程的形式表现出来了，所以它本质是数学，不是计算机算法。
从计算机算法的角度，结合我们大多数人的需求，这种秀智商的纯技巧题目绝对占少数，虽然很容易让人大呼精妙，但不能提炼出思考算法题的通用思维，真正通用的思维反而大道至简，就是穷举。
我记得自己一开始学习算法的时候，也觉得算法是一个很高大上的东西，每见到一道题，就想着能不能推导出一个什么数学公式，啪的一下就能把答案算出来。
比如你和一个没学过（计算机）算法的人说你写了个计算排列组合的算法，他大概以为你发明了一个公式，可以直接算出所有排列组合。但实际上呢？没什么高大上的公式，前文 回溯算法秒杀排列组合子集问题 写了，还是得用回溯算法暴力穷举。
对计算机算法的误解也许是以前学数学留下的「后遗症」，数学题一般都是你仔细观察，找几何关系，列方程，然后算出答案。如果说你需要进行大规模穷举来寻找答案，那大概率是你的解题思路出问题了。
而计算机解决问题的思维恰恰相反，有没有什么数学公式就交给你们人类去推导吧，但如果推导不出来，那就穷举呗，反正只要复杂度允许，没有什么答案是穷举不出来的。
技术岗笔试面试考的那些算法题，求个最大值最小值什么的，你怎么求？必须得把所有可行解穷举出来才能找到最值对吧，说白了不就这么点事儿么。
「穷举」具体来说可以分为两点，看到一道算法题，可以从这两个维度去思考：
1、如何穷举？
2、如何聪明地穷举？
不同类型的题目，难点是不同的，有的题目难在「如何穷举」，有的题目难在「如何聪明地穷举」。
什么算法的难点在「如何穷举」呢？一般是递归类问题，最典型的就是动态规划系列问题。
前文 动态规划核心套路 阐述了动态规划系列问题的核心原理，无非就是先写出暴力穷举解法（状态转移方程），加个备忘录就成自顶向下的动态规划解法了，再改一改就成自底向上的迭代解法了，动态规划的降维打击 里也讲过如何分析优化动态规划算法的空间复杂度。
上述过程就是在不断优化算法的时间、空间复杂度，也就是所谓「如何聪明地穷举」，这些技巧一听就会了。但很多读者留言说明白了这些原理，遇到动态规划题目还是不会做，因为第一步的暴力解法都写不出来。
这很正常，因为动态规划类型的题目可以千奇百怪，找状态转移方程才是难点，所以才有了 动态规划设计方法：最长递增子序列 这篇文章，告诉你递归穷举的核心是数学归纳法，明确函数的定义，然后利用这个定义写递归函数，就可以穷举出所有可行解。
什么算法的难点在「如何聪明地穷举」呢？一些耳熟能详的非递归算法技巧，都可以归在这一类。
比如前文 Union Find 并查集算法详解 告诉你一种高效计算连通分量的技巧，理论上说，想判断两个节点是否连通，我用 DFS/BFS 暴力搜索（穷举）肯定可以做到，但人家 Union Find 算法硬是用数组模拟树结构，给你把连通性相关的操作复杂度给干到O(1)了。
这就属于聪明地穷举，你学过就会用，没学过恐怕很难想出这种思路。
再比如贪心算法技巧，前文 当老司机学会贪心算法 就告诉你，所谓贪心算法就是在题目中发现一些规律（专业点叫贪心选择性质），使得你不用完整穷举所有解就可以得出答案。
人家动态规划好歹是无冗余地穷举所有解，然后找一个最值，你贪心算法可好，都不用穷举所有解就可以找到答案，所以前文 贪心算法解决跳跃游戏 中贪心算法的效率比动态规划还高。
再比如大名鼎鼎的 KMP 算法，你写个字符串暴力匹配算法很容易，但你发明个 KMP 算法试试？KMP 算法的本质是聪明地缓存并复用一些信息，减少了冗余计算，前文 KMP 字符匹配算法 就是使用状态机的思路实现的 KMP 算法。
下面我概括性地列举一些常见的算法技巧，供大家学习参考。
数组/单链表系列算法
单链表常考的技巧就是双指针，前文 单链表六大技巧 全给你总结好了，这些技巧就是会者不难，难者不会。
比如判断单链表是否成环，拍脑袋的暴力解是什么？就是用一个HashSet之类的数据结构来缓存走过的节点，遇到重复的就说明有环对吧。但我们用快慢指针可以避免使用额外的空间，这就是聪明地穷举嘛。
当然，对于找链表中点这种问题，使用双指针技巧只是显示你学过这个技巧，和遍历两次链表的常规解法从时间空间复杂度的角度来说都是差不多的。
数组常用的技巧有很大一部分还是双指针相关的技巧，说白了是教你如何聪明地进行穷举。
首先说二分搜索技巧，可以归为两端向中心的双指针。如果让你在数组中搜索元素，一个 for 循环穷举肯定能搞定对吧，但如果数组是有序的，二分搜索不就是一种更聪明的搜索方式么。
前文 二分搜索框架详解 给你总结了二分搜索代码模板，保证不会出现搜索边界的问题。前文 二分搜索算法运用 给你总结了二分搜索相关题目的共性以及如何将二分搜索思想运用到实际算法中。
类似的两端向中心的双指针技巧还有力扣上的 N 数之和系列问题，前文 一个函数秒杀所有 nSum 问题 讲了这些题目的共性，甭管几数之和，解法肯定要穷举所有的数字组合，然后看看那个数字组合的和等于目标和嘛。比较聪明的方式是先排序，利用双指针技巧快速计算结果。
再说说 滑动窗口算法技巧，典型的快慢双指针，快慢指针中间就是滑动的「窗口」，主要用于解决子串问题。
文中最小覆盖子串这道题，让你寻找包含特定字符的最短子串，常规拍脑袋解法是什么？那肯定是类似字符串暴力匹配算法，用嵌套 for 循环穷举呗，平方级的复杂度。
而滑动窗口技巧告诉你不用这么麻烦，可以用快慢指针遍历一次就求出答案，这就是教你聪明的穷举技巧。
但是，就好像二分搜索只能运用在有序数组上一样，滑动窗口也是有其限制的，就是你必须明确的知道什么时候应该扩大窗口，什么时候该收缩窗口。
比如前文 最大子数组问题 面对的问题就没办法用滑动窗口，因为数组中的元素存在负数，扩大或缩小窗口并不能保证窗口中的元素之和就会随着增大和减小，所以无法使用滑动窗口技巧，只能用动态规划技巧穷举了。
还有回文串相关技巧，如果判断一个串是否是回文串，使用双指针从两端向中心检查，如果寻找回文子串，就从中心向两端扩散。前文 最长回文子串 使用了一种技巧同时处理了回文串长度为奇数或偶数的情况。
当然，寻找最长回文子串可以有更精妙的马拉车算法（Manacher 算法），不过，学习这个算法的性价比不高，没什么必要掌握。
最后说说 前缀和技巧 和 差分数组技巧。
如果频繁地让你计算子数组的和，每次用 for 循环去遍历肯定没问题，但前缀和技巧预计算一个preSum数组，就可以避免循环。
类似的，如果频繁地让你对子数组进行增减操作，也可以每次用 for 循环去操作，但差分数组技巧维护一个diff数组，也可以避免循环。
数组链表的技巧差不多就这些了，都比较固定，只要你都见过，运用出来的难度不算大，下面来说一说稍微有些难度的算法。
二叉树系列算法
老读者都知道，二叉树的重要性我之前说了无数次，因为二叉树模型几乎是所有高级算法的基础，尤其是那么多人说对递归的理解不到位，更应该好好刷二叉树相关题目。
我之前说过，二叉树题目的递归解法可以分两类思路，第一类是遍历一遍二叉树得出答案，第二类是通过分解问题计算出答案，这两类思路分别对应着 回溯算法核心框架 和 动态规划核心框架。
什么叫通过遍历一遍二叉树得出答案？
就比如说计算二叉树最大深度这个问题让你实现maxDepth这个函数，你这样写代码完全没问题：
// 记录最大深度
int res = 0;
int depth = 0;
// 主函数
intmaxDepth(TreeNode root) {
traverse(root);
return res;
}
// 二叉树遍历框架
voidtraverse(TreeNode root) {
if (root ==null) {
// 到达叶子节点
res = Math.max(res, depth);
return;
}
// 前序遍历位置
depth++;
traverse(root.left);
traverse(root.right);
// 后序遍历位置
depth--;
}
这个逻辑就是用traverse函数遍历了一遍二叉树的所有节点，维护depth变量，在叶子节点的时候更新最大深度。
你看这段代码，有没有觉得很熟悉？能不能和回溯算法的代码模板对应上？
不信你照着 回溯算法核心框架 中全排列问题的代码对比下：
// 记录所有全排列
List<List<Integer>> res =new LinkedList<>();
LinkedList<Integer> track =new LinkedList<>();
/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {
backtrack(nums);
return res;
}
// 回溯算法框架
voidbacktrack(int[] nums) {
if (track.size() == nums.length) {
// 穷举完一个全排列
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
if (track.contains(nums[i]))
continue;
// 前序遍历位置做选择
track.add(nums[i]);
backtrack(nums);
// 后序遍历位置取消选择
track.removeLast();
}
}
前文讲回溯算法的时候就告诉你回溯算法本质就是遍历一棵多叉树，连代码实现都如出一辙有没有？
而且我之前经常说，回溯算法虽然简单粗暴效率低，但特别有用，因为如果你对一道题无计可施，回溯算法起码能帮你写一个暴力解捞点分对吧。
那什么叫通过分解问题计算答案？
同样是计算二叉树最大深度这个问题，你也可以写出下面这样的解法：
// 定义：输入根节点，返回这棵二叉树的最大深度
intmaxDepth(TreeNode root) {
if (root ==null) {
return 0;
}
// 递归计算左右子树的最大深度
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
// 整棵树的最大深度
int res = Math.max(leftMax, rightMax) + 1;
return res;
}
你看这段代码，有没有觉得很熟悉？有没有觉得有点动态规划解法代码的形式？
不信你看 动态规划核心框架 中凑零钱问题的暴力穷举解法：
// 定义：输入金额 amount，返回凑出 amount 的最少硬币个数
intcoinChange(int[] coins,int amount) {
// base case
if (amount == 0)return 0;
if (amount < 0)return -1;
int res = Integer.MAX_VALUE;
for (int coin : coins) {
// 递归计算凑出 amount - coin 的最少硬币个数
int subProblem = coinChange(coins, amount - coin);
if (subProblem == -1)continue;
// 凑出 amount 的最少硬币个数
res = Math.min(res, subProblem + 1);
}
return res == Integer.MAX_VALUE ? -1 : res;
}
这个暴力解法加个memo备忘录就是自顶向下的动态规划解法，你对照二叉树最大深度的解法代码，有没有发现很像？
动态规划系列问题有「最优子结构」和「重叠子问题」两个特性，而且一定是让你求最值的，然而很多算法虽然不属于动态规划，也符合分解问题的思维模式。
比如 分治算法详解 中说到的运算表达式优先级问题，其核心依然是大问题分解成子问题，只不过没有重叠子问题，不能用备忘录去优化效率罢了。
当然，除了动归、回溯（DFS）、分治，还有一个常用算法就是 BFS 了，前文 BFS 算法核心框架 就是根据下面这段二叉树的层序遍历代码改装出来的：
// 输入一棵二叉树的根节点，层序遍历这棵二叉树
voidlevelTraverse(TreeNode root) {
if (root ==null)return 0;
Queue<TreeNode> q =new LinkedList<>();
q.offer(root);
int depth = 1;
// 从上到下遍历二叉树的每一层
while (!q.isEmpty()) {
int sz = q.size();
// 从左到右遍历每一层的每个节点
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
if (cur.left !=null) {
q.offer(cur.left);
}
if (cur.right !=null) {
q.offer(cur.right);
}
}
depth++;
}
}
更进一步，图论相关的算法也是二叉树算法的延续。
比如 图论基础 和 环判断和拓扑排序 就用到了 DFS 算法；再比如 Dijkstra 算法模板，就是改造版 BFS 算法加上一个类似 dp table 的数组。
好了，说的差不多了，上述这些算法的本质都是穷举二（多）叉树，有机会的话通过剪枝或者备忘录的方式减少冗余计算，提高效率，就这么点事儿。
最后总结
上周在视频号直播的时候，有读者问我什么刷题方式是正确的，我说正确的刷题方式应该是刷一道题能获得刷十道题的效果，不然力扣现在 2000 道题目，你都打算刷完么？
那么怎么做到呢？学习数据结构和算法的框架思维 说了，要有框架思维，学会提炼重点，一个算法技巧可以包装出一百道题，如果你能一眼看穿它的本质，那就没必要浪费时间刷了嘛。
同时，在做题的时候要思考，联想，进而培养举一反三的能力。
前文 Dijkstra 算法模板 并不是真的是让你去背代码模板，不然的话直接甩出来那一段代码不就行了，我从层序遍历讲到 BFS 讲到 Dijkstra，说这么多废话干什么？
说到底我还是希望爱思考的读者能培养出成体系的算法思维，最好能爱上算法，而不是单纯地看题解去做题，授人以鱼不如授人以渔嘛。
本文就到这里吧，算法真的没啥难的，只要有心，谁都可以学好，欢迎大家关注我的视频号，每周周末我都会直播：
labuladong
感谢一路有你
喜欢作者
6 人喜欢
阅读 8587
分享收藏
赞116
在看30
写下你的留言
精选留言
梦溪置顶2我擦、恍然大悟，如醍醐灌顶，太强了，佬。labuladong(作者)3有帮助的话就点个在看分享给需要的朋友哦iwand先赞再看labuladong(作者)优秀Emma太强了你算哪块草莓夹心小饼干🌝 已分享给很多朋友，个人认为东哥本文的重点在于最后总结，才是学习算法刷题的关键。labuladong(作者)129_大道至简bkpp谢谢东哥 让我克服了对算法的恐惧 加油！labuladong(作者)加油～Oneey🧗真牛逼我的哥realLei是的，难住很多人的dfs 回溯 dp 实际上都是穷举，或者说是遍历，然后在遍历过程中找规律
已无更多数据
：，。视频小程序赞，轻点两下取消赞在看，轻点两下取消在看
评论区