Skip to content

Latest commit

 

History

History
310 lines (185 loc) · 20.2 KB

01.01.03-LeetCode-Guide.md

File metadata and controls

310 lines (185 loc) · 20.2 KB
Raw

01.01.03 LeetCode 入门及攻略（第 01 ~ 02 天）

1. LeetCode 是什么

「LeetCode」 是一个代码在线评测平台（Online Judge），包含了 算法、数据库、Shell、多线程 等不同分类的题目，其中以算法题目为主。我们可以通过解决 LeetCode 题库中的问题来练习编程技能，以及提高算法能力。

LeetCode 上有 $3000+$ 道的编程问题，支持 $16+$ 种编程语言（C、C++、Java、Python 等），还有一个活跃的社区，可以用于分享技术话题、职业经历、题目交流等。

并且许多知名互联网公司在面试的时候喜欢考察 LeetCode 题目，通常会以手写代码的形式出现。需要面试者对给定问题进行分析并给出解答，有时还会要求面试者分析算法的时间复杂度和空间复杂度，以及算法思路。面试官通过考察面试者对常用算法的熟悉程度和实现能力来确定面试者解决问题的思维能力水平。

所以无论是面试国内还是国外的知名互联网公司，通过 LeetCode 刷题，充分准备好算法，对拿到一个好公司的好 offer 都是有帮助的。

2. LeetCode 新手入门

2.1 LeetCode 注册

  1. 打开 LeetCode 中文主页，链接：力扣（LeetCode）官网。
  2. 输入手机号，获取验证码。
  3. 输入验证码之后，点击「登录 / 注册」，就注册好了。

LeetCode 注册页面

2.2 LeetCode 题库

「题库」是 LeetCode 上最直接的练习入口，在这里可以根据题目的标签、难度、状态进行刷题。也可以按照随机一题开始刷题。

LeetCode 题库页面

1. 题目标签

LeetCode 的题目涉及了许多算法和数据结构。有贪心，搜索，动态规划，链表，二叉树，哈希表等等，可以通过选择对应标签进行专项刷题，同时也可以看到对应专题的完成度情况。

LeetCode 题目标签

2. 题目列表

LeetCode 提供了题目的搜索过滤功能。可以筛选相关题单、不同难易程度、题目完成状态、不同标签的题目。还可以根据题目编号、题解数目、通过率、难度、出现频率等进行排序。

LeetCode 题目列表

3. 当前进度

当前进度提供了一个直观的进度展示。在这里可以看到自己的练习概况。进度会自动展现当前的做题情况。也可以点击「进度设置」创建新的进度，在这里还可以修改、删除相关的进度。

LeetCode 当前进度

4. 题目详情

从题目大相关题目点击进去，就可以看到这道题目的内容描述和代码编辑器。在这里还可以查看相关的题解和自己的提交记录。

LeetCode 题目详情

2.3 LeetCode 刷题语言

大厂在面试算法的时候考察的是基本功，用什么语言没有什么限制，也不会影响成绩。日常刷题建议使用自己熟悉的语言，或者语法简洁的语言刷题。

相对于 Java、Python 而言，C、C++ 相关的语法比较复杂，在做题的时候一方面需要思考思路，另一方面还要研究语法。并且复杂的语法也不利于看懂思路，耗费时间较多，不利于刷题效率。在面试的时候往往需要一个小时内尽可能的完成更多的题目，C++ 一旦语法出错很容易慌乱。当然 LeetCode 周赛的大神更偏向于使用 C++ 刷题，这是因为用 C++ 参加算法竞赛已经成为传统了，绝大多数的 OI / ACM 竞赛选手都是 C++ 大神。

就我个人经历而言，我大学参加 ACM 竞赛的时候，用的是 C、C++ 和一点点的 Java。现在刷 LeetCode 为了更高的刷题效率，选择了 Python。感觉用 Python 刷题能更加专注于算法与数据结构本身，也能获得更快的刷题效率。

人生苦短，我用 Python。

2.4 LeetCode 刷题流程

在「2.2 LeetCode 题库 —— 4. 题目详情」中我们介绍了题目的相关情况。

LeetCode 题目详情

可以看到左侧区域为题目内容描述区域，在这里可以看到题目的内容描述和一些示例数据。而右侧是代码编辑区域，代码编辑区域里边默认显示了待实现的方法。

我们需要在代码编辑器中根据方法给定的参数实现对应的算法，并返回题目要求的结果。然后还要经过「执行代码」测试结果，点击「提交」后，显示执行结果为「通过」时，才算完成一道题目。

LeetCode 提交记录

总结一下我们的刷题流程为：

  1. 在 LeetCode 题库中选择一道自己想要解决的题目。
  2. 查看题目左侧的题目描述，理解题目要求。
  3. 思考解决思路，并在右侧代码编辑区域实现对应的方法，并返回题目要求的结果。
  4. 如果实在想不出解决思路，可以查看题目相关的题解，努力理解他人的解题思路和代码。
  5. 点击「执行代码」按钮测试结果。
    • 如果输出结果与预期结果不符，则回到第 3 步重新思考解决思路，并改写代码。
  6. 如果输出结果与预期符合，则点击「提交」按钮。
    • 如果执行结果显示「编译出错」、「解答错误」、「执行出错」、「超出时间限制」、「超出内存限制」等情况，则需要回到第 3 步重新思考解决思路，或者思考特殊数据，并改写代码。
  7. 如果执行结果显示「通过」，恭喜你通过了这道题目。

接下来我们将通过「1. 两数之和 - 力扣（LeetCode）」这道题目来讲解如何在 LeetCode 上刷题。

2.5 LeetCode 第一题

2.5.1 题目链接

2.5.2 题目大意

描述：给定一个整数数组 $nums$ 和一个整数目标值 $target$。

要求：在该数组中找出和为 $target$ 的两个整数，并输出这两个整数的下标。可以按任意顺序返回答案。

说明：

  • $2 \le nums.length \le 10^4$。
  • $-10^9 \le nums[i] \le 10^9$。
  • $-10^9 \le target \le 10^9$。
  • 只会存在一个有效答案。

示例：

  • 示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
  • 示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

2.5.3 解题思路

思路 1：枚举算法
  1. 使用两重循环枚举数组中每一个数 $nums[i]$、$nums[j]$，判断所有的 $nums[i] + nums[j]$ 是否等于 $target$。
  2. 如果出现 $nums[i] + nums[j] == target$，则说明数组中存在和为 $target$ 的两个整数，将两个整数的下标 $i$、$j$ 输出即可。
思路 1：代码
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if i != j and nums[i] + nums[j] == target:
                    return [i, j]
        return []
思路 1：复杂度分析
  • 时间复杂度：$O(n^2)$，其中 $n$ 是数组 $nums$ 的元素数量。
  • 空间复杂度：$O(1)$。
思路 2：哈希表

哈希表中键值对信息为 $target - nums[i]: i$，其中 $i$ 为下标。

  1. 遍历数组，对于每一个数 $nums[i]$：
    1. 先查找字典中是否存在 $target - nums[i]$，存在则输出 $target - nums[i]$ 对应的下标和当前数组的下标 $i$。
    2. 不存在则在字典中存入 $target - nums[i]$ 的下标 $i$。
思路 2：代码
def twoSum(self, nums: List[int], target: int) -> List[int]:
    numDict = dict()
    for i in range(len(nums)):
        if target-nums[i] in numDict:
            return numDict[target-nums[i]], i
        numDict[nums[i]] = i
    return [0]
思路 2：复杂度分析
  • 时间复杂度：$O(n)$，其中 $n$ 是数组 $nums$ 的元素数量。
  • 空间复杂度：$O(n)$。

理解了上面这道题的题意，就可以试着自己编写代码，并尝试提交通过。也可以通过我的解题思路和解题代码，理解之后进行编写代码，并尝试提交通过。

如果提交结果显示「通过」，那么恭喜你完成了 LeetCode 上的第一题。虽然只是一道题，但这意味着刷题计划的开始！希望你能坚持下去，得到应有的收获。

3. LeetCode 刷题攻略

3.1 LeetCode 前期准备

如果你是一个对基础算法和数据结构完全不懂的小白，那么在刷 LeetCode 之前，建议先学习一下基础的 「数据结构」 和 「算法」 知识，这样在开始刷题的时候才不会那么痛苦。

基础的 「数据结构」 和 「算法」 知识包括：

  • 常考的数据结构：数组、字符串、链表、树（如二叉树） 等。
  • 常考的算法：分治算法、贪心算法、穷举算法、回溯算法、动态规划 等。

这个阶段推荐看一些经典的算法基础书来进行学习。这里推荐一下我看过的感觉不错的算法书：

当然，也可以直接看我写的「算法通关手册」，欢迎指正和提出建议，万分感谢。

3.2 LeetCode 刷题顺序

讲个笑话，从前有个人以为 LeetCode 的题目是按照难易程度排序的，所以他从「1. 两数之和」 开始刷题，结果他卡在了 「4. 寻找两个正序数组的中位数」这道困难题上。

LeetCode 的题目序号并不是按照难易程度进行排序的，所以除非硬核人士，不建议按照序号顺序刷题。如果是新手刷题的话，推荐先从「简单」难度等级的算法题开始刷题。等简单题上手熟练之后，再开始按照标签类别，刷中等难度的题。中等难度的题刷差不多之后，可以考虑刷面试题或者难题。

其实 LeetCode 官方网站上就有整理好的题目不错的刷题清单。链接为：https://leetcode.cn/leetbook/。可以先刷这里边的题目卡片。我这里也做了一个整理。

推荐刷题顺序和目录如下：

1. 初级算法、2. 数组类算法、3. 数组和字符串、4. 链表类算法、5. 哈希表、6. 队列 & 栈、7. 递归、8. 二分查找、9. 二叉树、10. 中级算法、11. 高级算法、12. 算法面试题汇总。

当然还可以通过官方新推出的「学习计划 - 力扣」按计划每天刷题。

或者直接按照我整理的分类刷题列表进行刷题：

正在准备面试、没有太多时间刷题的小伙伴，可以按照我总结的「LeetCode 面试最常考 100 题」、「LeetCode 面试最常考 200 题」进行刷题。

说明：「LeetCode 面试最常考 100 题」、「LeetCode 面试最常考 200 题」是笔者根据「CodeTop 企业题库」按频度从高到低进行筛选，并且去除了一部分 LeetCode 上没有的题目和重复题目后得到的题目清单。

3.3 LeetCode 刷题技巧

下面分享一下我在刷题过程中用到的刷题技巧。简单来说，可以分为 $5$ 条：

  1. 五分钟思考法
  2. 重复刷题
  3. 按专题分类刷题
  4. 写解题报告
  5. 坚持刷题

3.3.1 五分钟思考法

五分钟思考法：如果一道题如果 $5$ 分钟之内有思路，就立即动手写代码解题。如果 $5$ 分钟之后还没有思路，就直接去看题解。然后根据题解的思路，自己去实现代码。如果发现自己看了题解也无法实现代码，就认真阅读题解的代码，并理解代码的逻辑。

这种刷题方法其实跟英语里边的背单词过程是类似的。

一开始零基础学英语的时候，先学最简单的字母，不用纠结为什么这个字母这么写。然后学习简单的单词，也不用去纠结这个单词为啥就是这个意思，学就完事。在掌握了基本词汇之后，再去学习词组，学习短句子，然后长句子，再然后再看文章。

而且，在学英语单词的时候，也不是学一遍就会了。而是不断的重复练习、重复记忆加深印象。

算法刷题也是一样，零基础刷题的时候，不要过分纠结怎么自己就想不出来算法的解法，怎么就想不到更加高效的方法。遇到没有思路的题目，老老实实去看题解区的高赞题解，尽可能的让自己快速入门。

3.3.2 重复刷题

重复刷题：遇见不会的题，多刷几遍，不断加深理解。

算法题有时候一遍刷过去，过的时间长了可能就忘了，看到之前做的题不能够立马想到解题思路。这其实还是跟背单词一样，单词也不是看一遍就完全记住了。所以题目刷完一遍并不是结束了，还需要不断的回顾。

而且，一道题目可能有多种解法，还可能有好的算法思路。

最开始做的时候，可能只能想到一种思路，再做第二遍的时候，很有可能会想到了新的解法，新的优化方式等等。

所以，算法题在做完一遍之后遇见不会的，还可以多刷几遍，不断加深理解。

3.3.3 按专题分类刷题

按专题分类刷题：按照不同专题分类刷题，既可以巩固刚学完的算法知识，还可以提高刷题效率。

在上边「3.2 LeetCode 刷题顺序」我们给出了刷题顺序和目录。这里的刷题顺序其实就是按照不同分类来进行排序的。

我们可以在学习相关算法和数据结构知识时，顺便做一下该算法和数据结构知识专题下对应的题目清单。比如在学习完「链表」相关的基础知识时，可以将「链表」相关的基础题目刷完，或者刷官方 LeetBook 清单 4. 链表类算法 中的对应题目。

按照专题分类刷题的第一个好处是：可以巩固刚学完的算法知识。 如果是第一次学习对应的算法知识，刚学完可能对里边的相关知识理解的不够透彻，或者说可能会遗漏一些关键知识点，这时候可以通过刷对应题目的方式来帮助我们巩固刚学完的算法知识。

按照专题分类刷题的第二个好处是：可以提高刷题效率。 因为同一类算法题目所用到的算法知识其实是相同或者相似的，同一种解题思路可以运用到多道题目中。通过不断求解同一类算法专题下的题目，可以大大的提升我们的刷题速度。

3.3.4 写解题报告

写解题报告：如果能够用简介清晰的语言让别人听懂这道题目的思路，那就说明你真正理解了这道题的解法。

刷算法题，有一个十分有用的技巧，就是 「写解题报告」。如果你刷完一道题，能把这道题的解题步骤，做题思路用通俗易懂的话写成解题报告，那么这道题就算是掌握了。这其实就相当于「费曼学习法」的思维。

这样，也可以减少刷题的遍数。如果在写题的时候遇到之前刷过的题，但一时之间没有思路的，就可以看看自己之前的解题报告。这样就节省了大量重复刷题的时间。

3.3.5 坚持刷题

坚持刷题：算法刷题没有捷径，只有不断的刷题、总结，再刷题，再总结。

千万不要相信很多机构宣传的「3 天带你精通数据结构」、「7 天从算法零基础到精通」能让你快速学会算法知识。

学习算法和数据结构知识，不能靠速成，只能靠不断的积累，一步一步的推敲算法步骤，一遍又一遍的理解算法思想，才能掌握一个又一个的算法知识。而且还要不断的去刷该算法对应专题下的题目，才能将算法知识应用到日常的解题过程中。这样才能算彻底掌握了一个算法或一种解题思路。

根据我过去一年多和小伙伴们一起刷题打卡的经验发现：那些能够坚持每天刷题，并最终学会一整套「基础算法知识」和「基础数据结构知识」的人，总是少数人。

大部分总会因为种种主观和客观原因而放弃了刷题（工作繁忙、学习任务繁重、个人精力有限、时间不足等）。

但不管怎么样，如果你当初选择了学习算法知识，选择了通过刷题来通过面试，以便获取更好的工作岗位。那我希望在达成自己的目标之前，可以一直坚持下去，去「刻意练习」。在刷题的过程中收获知识，通过刷题得到满足感，从而把刷题变成兴趣。

这些话有些鸡汤了，但都是我的心里话。希望大家能够一起坚持刷题，争取早日实现自己的目标。

参考资料