点击
机器学习算
法与Python学习 ，
选择加星标
精彩内容不迷路
很多朋友害怕算法，其实大可不必，算法题无非就那几个套路，一旦掌握，就会觉得算法实在是太朴实无华且枯燥了！本文选自硬核算法教程《labuladong的算法小抄》，带你学习套路，把握各类算法问题的共性！数据结构是工具，算法是通过合适的工具解决特定问题的方法。对于任何数据结构，其基本操作无非遍历 + 访问，再具体一点就是：增、删、查、改。那么该如何在力扣刷题呢？很多文章都会告诉你“按标签刷”“坚持下去”等。不说这些不痛不痒的话，直接给具体的建议。
这是我刷题一年的亲身体会，下图是 2019 年 10 月的提交截图：据我观察，大部分人对与数据结构相关的算法文章不感兴趣，而是更关心动态规划、回溯、分治等技巧。这是不对的，这些常考算法技巧在《labuladong的算法小抄》中都会有所涉及，到时候你就会发现，它们看起来高大上，但本质上就是一个多叉树遍历的问题，配合算法框架，并没有多难。因为二叉树是最容易培养框架思维的，而且大部分常考算法本质上都是树的遍历问题。其实大家不是没思路，只是没有理解“框架”是什么。不要小看下面这几行代码，几乎所有二叉树的题目一套用这个框架就都出来了。1void traverse(TreeNode root) {
2 // 前序遍历
3 traverse(root.left);
4 // 中序遍历
5 traverse(root.right);
6 // 后序遍历
7}
比如随便拿几道题的解法代码出来，这里不用管具体的代码逻辑，只看看框架在其中是如何发挥作用的。 LeetCode 124 题 ，难度为 Hard，求二叉树中最大路径和，主要代码如下： 1int ans = INT_MIN;
2int oneSideMax(TreeNode* root) {
3 if (root == nullptr) return 0;
4
5 int left = max(0, oneSideMax(root->left));
6 int right = max(0, oneSideMax(root->right));
7
8 /**** 后序遍历 ****/
9 ans = max(ans, left + right + root->val);
10 return max(left, right) + root->val;
11 /****************/
12}
那为什么是后序呢？题目要求最大路径和，对于一个二叉树节点，是不是先计算左子树和右子树的最大路径和，然后加上自己的值，这样就得出新的最大路径和了？所以说这里就要使用后续遍历框架。 LeetCode 105 题 ，难度为 Medi um，要求根据前序遍历和中序遍历的结果还原一棵二叉树，这是很经典的问题，主要代码如下： 1TreeNode buildTree(int[] preorder, int preStart, int preEnd,
2 int[] inorder, int inStart, int inEnd, Map inMap) {
3
4 if(preStart > preEnd || inStart > inEnd) return null;
5
6 /**** 前序遍历 ****/
7 TreeNode root = new TreeNode(preorder[preStart]);
8 int inRoot = inMap.get(root.val);
9 int numsLeft = inRoot - inStart;
10 /****************/
11
12 root.left = buildTree(preorder, preStart + 1, preStart + numsLeft,
13 inorder, inStart, inRoot - 1, inMap);
14 root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd,
15 inorder, inRoot + 1, inEnd, inMap);
16 return root;
17}
不要看这个函数的参数很多，它们只是为了控制数组索引而已，本质上该算法就是一个前序遍历算法。 LeetCode 99 题 ，难度为 Hard，要求恢复一棵 BST（完全二叉树），主要代码如下： 1void traverse(TreeNode* node) {
2 if (!node) return;
3
4 traverse(node->left);
5
6 /****中序遍历 ****/
7 if
(node->val val) {
8 s = (s == NULL) ? prev : s;
9 t = node;
10 }
11 prev = node;
12 /****************/
13
14 traverse(node->right);
15}
这不就是中序遍历嘛，对于一棵 BST，中序遍历意味着什么，应该不需要解释了吧。你看，Hard 难度的题目不过如此，而且还这么有规律可循，只要把框架写出来，然后往相应的位置加内容就行了，这不就是思路嘛！对于一个理解二叉树的人来说，刷一道二叉树的题目花不了多长时间。那么如果你对刷题无从下手或者有畏惧心理，不妨从二叉树下手，前 10 道也许有点难受；结合框架再做 20 道题，也许你就有点自己的理解了；刷完整个专题，再去做什么回溯、动态规化、分治专题，你就会发现只要涉及递归的问题，基本上都是树的问题。在《labuladong的算法小抄》“动态规划解题套路框架”章节中，会讲到凑零钱问题，暴力解法就是遍历一棵 N 叉树： 1def coinChange(coins: List[int], amount: int):
2
3 def dp(n):
4 if n == 0: return 0
5 if n 0: return -1
6
7 res = float( INF )
8 for coin in coins:
9 subproblem = dp(n - coin)
10 # 子问题无解，跳过
11 if subproblem == -1: continue
12 res = min(res, 1 + subproblem)
13 return res if res != float( INF ) else -1
14
15 return dp(amount)
这么多代码看不懂怎么办？直接提取框架，这样就能看出核心思路了，这就是刚才说到的遍历 N 叉树的框架：1def dp(n):
2 for coin in coins:
3 dp(n - coin)
其实很多动态规划问题就是在遍历一棵树，你如果对树的遍历操作烂熟于心，那么起码知道怎么把思路转化成代码，也知道如何提取别人解法的核心思路。再看看回溯算法，在《labuladong的算法小抄》“回溯算法解题套路框架”中会直接告诉你，回溯算法就是一个 N 叉树的前序 + 后序遍历问题，没有例外。比如，排列组合问题、经典的回溯问题，主要代码如下： 1void
backtrack(int[] nums, LinkedList track) {
2 if (track.size() == nums.length) {
3 res.add(new LinkedList(track));
4 return;
5 }
6
7 for (int i = 0; i 8 if (track.contains(nums[i]))
9 continue;
10 track.add(nums[i]);
11 // 进入下一层决策树
12 backtrack(nums, track);
13 track.removeLast();
14 }
15
16/* 提取 N叉树遍历框架 */
17void backtrack(int[] nums, LinkedList track) {
18 for (int i = 0; i 19 backtrack(nums, track);
20}
N 叉树的遍历框架，找出来了吧。
你说，树这种结构重不重要？综上所述，对于畏惧算法或者刷题很多但依然感觉不得要领的朋友来说，可以先刷树的相关题目，试着从框架看问题，而不要纠结于细节。所谓纠结细节，就比如纠结 i 到底应该加到 n 还是加到 n - 1 ，这个数组的大小到底应该开成 n 还是 n + 1 ？从框架看问题，就是像我们这样基于框架进行抽取和扩展，既可以在看别人解法时快速理解核心逻辑，也有助于我们找到自己写解法时的思路方向。当然，如果细节出错，你将得不到正确的答案，但是只要有框架，再错也错不到哪去，因为你的方向是对的。但是，你要是心中没有框架，那么根本无法解题，给你答案，也不能意识到这就是树的遍历问题。框架思维是很重要的，有时候按照流程写出解法，说实话我自己都不知道为啥是对的，反正它就是对了……这就是框架的力量，能够保证你在思路不那么清晰的时候，依然写出正确的程序。最后我们总结一下，刷算法题建议从“树”分类开始刷，结合框架思维，把几十道题刷完，对于树结构的理解应该就到位了。这时候去看回溯、动态规划、分治等算法专题，对思路的理解可能会更加深刻一些。在思考问题的过程中，少纠结细节，不要热衷于炫技；希望读者多从框架看问题，多学习套路，把握各类算法问题的共性，《labuladong的算法小抄》将会为你提供这方面的帮助。
参与方式：文末留言，赞数最多的3位为本次中奖者
开奖时间：2021年2月2号20点
备注：如有问题，请添加小助手微信：MLAPython，备注（姓名-单位-研究方向）
