我的刷题经验总结智能合约

-----------
两年前刚开这个公众号的时候，我写了一篇学习数据结构和算法的框架思维，现在已经 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> res = new LinkedList<>(); LinkedList track = new LinkedList<>(); /* 主函数，输入一组不重复的数字，返回它们的全排列 */ List> 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 res = new LinkedList<>(); // 前序遍历函数 List 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 preorder(TreeNode root) { List 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 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，说这么多废话干什么？
说到底我还是希望爱思考的读者能培养出成体系的算法思维，最好能爱上算法，而不是单纯地看题解去做题，授人以鱼不如授人以渔嘛。
本文就到这里吧，算法真的没啥难的，只要有心，谁都可以学好。分享是一种美德，如果本文对你有启发，欢迎分享给需要的朋友。
＿＿＿＿＿＿＿＿＿＿＿＿＿