共计 6944 个字符，预计需要花费 18 分钟才能阅读完成。
———–
两年前刚开这个公众号的时候，我写了一篇 学习数据结构和算法的框架思维，当初曾经 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;
// 主函数
int maxDepth(TreeNode root) {traverse(root);
return res;
}
// 二叉树遍历框架
void traverse(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;
}
// 回溯算法框架
void backtrack(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();}
}前文讲回溯算法的时候就通知你回溯算法实质就是遍历一棵多叉树，连代码实现都一模一样有没有？
而且我之前常常说，回溯算法尽管简略粗犷效率低，但特地有用，因为如果你对一道题机关用尽，回溯算法起码能帮你写一个暴力解捞点分对吧。
那什么叫通过合成问题计算答案 ？
同样是计算二叉树最大深度这个问题，你也能够写出上面这样的解法：
// 定义：输出根节点，返回这棵二叉树的最大深度
int maxDepth(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 的起码硬币个数
int coinChange(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 备忘录就是自顶向下的动静布局解法，你对照二叉树最大深度的解法代码，有没有发现很像？
如果你感触到最大深度这个问题两种解法的区别，那就趁热打铁，我问你，二叉树的前序遍历怎么写 ？
我置信大家都会对这个问题不屑一顾，毫不犹豫就能够写出上面这段代码：
List<Integer> res = new LinkedList<>();
// 前序遍历函数
List<Integer> preorder(TreeNode root) {traverse(root);
return res;
}
// 二叉树遍历函数
void traverse(TreeNode root) {if (root == null) {return;}
// 前序遍历地位
res.addLast(root.val);
traverse(root.left);
traverse(root.right);
}然而，你联合下面说到的两种不同的思维模式，二叉树的遍历是否也能够通过合成问题的思路解决呢？
咱们前文 手把手刷二叉树（第二期）说过前中后序遍历后果的特点：
你留神前序遍历的后果，根节点的值在第一位，前面接着左子树的前序遍历后果，最初接着右子树的前序遍历后果 。
有没有领会出点什么来？其实齐全能够重写前序遍历代码，用合成问题的模式写进去，防止内部变量和辅助函数：
// 定义：输出一棵二叉树的根节点，返回这棵树的前序遍历后果
List<Integer> preorder(TreeNode root) {List<Integer> res = new LinkedList<>();
if (root == null) {return res;}
// 前序遍历的后果，root.val 在第一个
res.add(root.val);
// 前面接着左子树的前序遍历后果
res.addAll(preorder(root.left));
// 最初接着右子树的前序遍历后果
res.addAll(preorder(root.right));
}你看，这就是用合成问题的思维模式写二叉树的前序遍历，如果写中序和后序遍历也是相似的。
当然，动静布局系列问题有「最优子结构」和「重叠子问题」两个个性，而且大多是让你求最值的。很多算法尽管不属于动静布局，但也合乎合成问题的思维模式。
比方 分治算法详解 中说到的运算表达式优先级问题，其外围仍然是大问题分解成子问题，只不过没有重叠子问题，不能用备忘录去优化效率罢了。
当然，除了动归、回溯（DFS）、分治，还有一个罕用算法就是 BFS 了，前文 BFS 算法外围框架 就是依据上面这段二叉树的层序遍历代码改装进去的：
// 输出一棵二叉树的根节点，层序遍历这棵二叉树
void levelTraverse(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，说这么多废话干什么？
说到底我还是心愿爱思考的读者能造就出成体系的算法思维，最好能爱上算法，而不是单纯地看题解去做题，授人以鱼不如授人以渔嘛。
本文就到这里吧， 算法真的没啥难的，只有有心，谁都能够学好 。分享是一种美德，如果本文对你有启发，欢送分享给须要的敌人。
_____________
查看更多优质算法文章 点击我的头像，手把手带你刷力扣，致力于把算法讲清楚！我的 算法教程 曾经取得 90k star，欢送点赞！