Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >算法刷题指南,来自GitHub 68.8k star的硬核算法教程

算法刷题指南,来自GitHub 68.8k star的硬核算法教程

作者头像
昱良
发布于 2021-02-09 13:20:04
发布于 2021-02-09 13:20:04
1.1K00
代码可运行
举报
运行总次数:0
代码可运行

很多朋友害怕算法,其实大可不必,算法题无非就那几个套路,一旦掌握,就会觉得算法实在是太朴实无华且枯燥了!

本文选自硬核算法教程《labuladong的算法小抄》,带你学习套路,把握各类算法问题的共性!

数据结构是工具,算法是通过合适的工具解决特定问题的方法。对于任何数据结构,其基本操作无非遍历 + 访问,再具体一点就是:增、删、查、改。

那么该如何在力扣刷题呢?很多文章都会告诉你“按标签刷”“坚持下去”等。不说这些不痛不痒的话,直接给具体的建议。

先刷二叉树

先刷二叉树

!!先刷二叉树!!

这是我刷题一年的亲身体会,下图是 2019 年 10 月的提交截图:

据我观察,大部分人对与数据结构相关的算法文章不感兴趣,而是更关心动态规划、回溯、分治等技巧。这是不对的,这些常考算法技巧在《labuladong的算法小抄》中都会有所涉及,到时候你就会发现,它们看起来高大上,但本质上就是一个多叉树遍历的问题,配合算法框架,并没有多难。

  • 为什么要先刷二叉树呢?

因为二叉树是最容易培养框架思维的,而且大部分常考算法本质上都是树的遍历问题。

  • 刷二叉树时看到题目没思路?

其实大家不是没思路,只是没有理解“框架”是什么。不要小看下面这几行代码,几乎所有二叉树的题目一套用这个框架就都出来了。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
1void traverse(TreeNode root) {
2    // 前序遍历
3    traverse(root.left);
4    // 中序遍历
5    traverse(root.right);
6    // 后序遍历
7}

比如随便拿几道题的解法代码出来,这里不用管具体的代码逻辑,只看看框架在其中是如何发挥作用的。

LeetCode 124 题 ,难度为 Hard,求二叉树中最大路径和,主要代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
 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,要求根据前序遍历和中序遍历的结果还原一棵二叉树,这是很经典的问题,主要代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
 1TreeNode buildTree(int[] preorder, int preStart, int preEnd, 
 2    int[] inorder, int inStart, int inEnd, Map<Integer, Integer> 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(完全二叉树),主要代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
 1void traverse(TreeNode* node) {
 2    if (!node) return;
 3
 4    traverse(node->left);
 5
 6    /****中序遍历 ****/
 7    if (node->val < prev->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 叉树:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
 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 叉树的框架:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
1def dp(n):
2    for coin in coins:
3        dp(n - coin)

其实很多动态规划问题就是在遍历一棵树,你如果对树的遍历操作烂熟于心,那么起码知道怎么把思路转化成代码,也知道如何提取别人解法的核心思路。

再看看回溯算法,在《labuladong的算法小抄》“回溯算法解题套路框架”中会直接告诉你,回溯算法就是一个 N 叉树的前序 + 后序遍历问题,没有例外。比如,排列组合问题、经典的回溯问题,主要代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
 1void backtrack(int[] nums, LinkedList<Integer> track) {
 2    if (track.size() == nums.length) {
 3        res.add(new LinkedList(track));
 4        return;
 5    }
 6
 7    for (int i = 0; i < nums.length; 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<Integer> track) {
18    for (int i = 0; i < nums.length; i++) {
19        backtrack(nums, track);
20}

N 叉树的遍历框架,找出来了吧。你说,树这种结构重不重要?

综上所述,对于畏惧算法或者刷题很多但依然感觉不得要领的朋友来说,可以先刷树的相关题目,试着从框架看问题,而不要纠结于细节。

所谓纠结细节,就比如纠结 i 到底应该加到 n 还是加到 n - 1 ,这个数组的大小到底应该开成 n 还是 n + 1 ?

从框架看问题,就是像我们这样基于框架进行抽取和扩展,既可以在看别人解法时快速理解核心逻辑,也有助于我们找到自己写解法时的思路方向。

当然,如果细节出错,你将得不到正确的答案,但是只要有框架,再错也错不到哪去,因为你的方向是对的。但是,你要是心中没有框架,那么根本无法解题,给你答案,也不能意识到这就是树的遍历问题。

框架思维是很重要的,有时候按照流程写出解法,说实话我自己都不知道为啥是对的,反正它就是对了……

这就是框架的力量,能够保证你在思路不那么清晰的时候,依然写出正确的程序。

—— ——

最后我们总结一下,刷算法题建议从“树”分类开始刷,结合框架思维,把几十道题刷完,对于树结构的理解应该就到位了。这时候去看回溯、动态规划、分治等算法专题,对思路的理解可能会更加深刻一些。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-01-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 机器学习算法与Python学习 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
东哥手把手帮你刷通二叉树|第二期
上篇文章 手把手教你刷二叉树(第一篇) 连刷了三道二叉树题目,很多读者直呼内行。其实二叉树相关的算法真的不难,本文再来三道,手把手带你看看树的算法到底怎么做。
labuladong
2021/09/23
2430
labuladong的算法小抄之js实现-第0章-学习算法和刷题的框架思维
文章直达地址: https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/xue-xi-shu-ju-jie-gou-he-suan-fa-de-gao-xiao-fang-fa
用户1974410
2022/09/20
3390
【算法】499- 数据结构和算法学习指南
这是好久之前的一篇文章 学习数据结构的框架思维 的修订版。之前那篇文章收到广泛好评,没看过也没关系,这篇文章会涵盖之前的所有内容,并且会举很多代码的实例,谈谈如何使用框架思维,并且给对于算法无从下手的朋友给一点具体可执行的刷题建议。
pingan8787
2020/02/18
4470
六道入门树题目带你走入树结构的世界
需要修改一些条件,只需要在返回结果加上一个或者条件,tree1和tree2的左右子树分别比较即可
冷环渊
2022/04/06
1960
六道入门树题目带你走入树结构的世界
数据结构和算法学习指南
这篇文章会涵盖之前的所有内容,并且会举很多代码的实例,谈谈如何使用框架思维,并且给对于算法无从下手的朋友给一点具体可执行的刷题建议。
五分钟学算法
2020/02/24
7170
剑指offer:重建二叉树
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
帅地
2019/03/11
2.2K0
重建二叉树
该文讲述了如何通过递归的方法重建二叉树。首先,介绍了递归的基本思路,然后给出了具体的代码实现。通过一个例子来演示了如何通过递归的方法构建二叉树。
用户1148830
2018/01/03
6460
图解「剑指Offer」之用前序和中序遍历序列构建二叉树
题目中给出的是 前序 + 中序 的组合,那么我们仔细观察对比一下 前序遍历 与 中序遍历。
五分钟学算法
2019/08/30
3.8K0
图解「剑指Offer」之用前序和中序遍历序列构建二叉树
[labuladong算法小抄]手把手带你刷二叉树(第一期)
我们公众号的成名之作 学习数据结构和算法的框架思维 中多次强调,先刷二叉树的题目,先刷二叉树的题目,先刷二叉树的题目,因为很多经典算法,以及我们前文讲过的所有回溯、动归、分治算法,其实都是树的问题,而树的问题就永远逃不开树的递归遍历框架这几行破代码:
唯一Chat
2021/02/25
9980
[labuladong算法小抄]手把手带你刷二叉树(第一期)
leetcode刷题(97)——105. 从前序与中序遍历序列构造二叉树
通过上面的图观察规律,前序遍历第一个值肯定是根结点,中序遍历,根结点左边都是左子树,右边都是右子树
老马的编程之旅
2022/06/22
1880
leetcode刷题(97)——105. 从前序与中序遍历序列构造二叉树
【数据结构与算法】一起搞定面试中的二叉树题目(二)
作者:IOExceptioner 本文继续一起搞定面试中的二叉树(一)一文总结二叉树相关的面试题。 12. 二叉树的前序遍历 迭代解法 ArrayList<Integer> preOrder(TreeNode root){ Stack<TreeNode> stack = new Stack<TreeNode>(); ArrayList<Integer> list = new ArrayList<Integer>(); if(root == null){ return l
用户1634449
2018/10/18
5520
东哥手把手带你刷二叉树|第三期
接前文 手把手带你刷二叉树(第一期)和 手把手带你刷二叉树(第二期),本文继续来刷二叉树。
labuladong
2021/09/23
6270
LeetCode通关:连刷三十九道二叉树,刷疯了!
大家好,我是拿输出博客来督促自己刷题的老三,这一节我们来刷二叉树,二叉树相关题目在面试里非常高频,而且在力扣里数量很多,足足有几百道,不要慌,我们一步步来。我的文章很长,你们 收藏一下。
三分恶
2021/09/08
8570
剑指offer--重建二叉树
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
AI那点小事
2020/04/18
2840
东哥手把手带你套框架刷通二叉树|第一期
我们公众号的成名之作 学习数据结构和算法的框架思维 中多次强调,先刷二叉树的题目,先刷二叉树的题目,先刷二叉树的题目,因为很多经典算法,以及我们前文讲过的所有回溯、动归、分治算法,其实都是树的问题,而树的问题就永远逃不开树的递归遍历框架这几行破代码:
labuladong
2021/09/23
5940
二叉树八股文:递归改迭代通用模板
之前经常讲涉及递归的算法题,我说过写递归算法的一个技巧就是不要试图跳进递归细节,而是从递归框架上思考,从函数定义去理解递归函数到底该怎么实现。
labuladong
2021/09/23
4370
LintCode 前序遍历和中序遍历树构造二叉树题目代码
题目 根据前序遍历和中序遍历树构造二叉树. 注意事项 你可以假设树中不存在相同数值的节点 样例 给出中序遍历:[1,2,3]和前序遍历:[2,1,3]. 返回如下的树: 2 / 1 3 代码 /** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { *
desperate633
2018/08/22
2200
leetcode刷题(97)——106. 从中序与后序遍历序列构造二叉树
这样的遍历顺序差异,导致了preorder和inorder数组中的元素分布有如下特点:
老马的编程之旅
2022/06/22
1740
leetcode刷题(97)——106. 从中序与后序遍历序列构造二叉树
我的刷题经验总结
两年前刚开这个公众号的时候,我写了一篇 学习数据结构和算法的框架思维,现在已经 5w 多阅读了,这对于一篇纯技术文来说是很牛逼的数据。
labuladong
2021/10/14
7990
通过前序+中序和后序+中序来构建二叉树
首先我们要知道,三种不同遍历方式的过程。看下图很容易理解,并且不容易忘。 前序遍历:根 左 右 中序遍历:左 根 右 后序遍历:左 右 根
帅地
2019/12/24
2.5K0
推荐阅读
相关推荐
东哥手把手帮你刷通二叉树|第二期
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验