零基础力扣学习

  这篇内容基本来源于力扣官方在知乎给萌新学习力扣的建议。
  在开始刷题前,只需要你至少掌握一门编程语言,即使你从未刷过算法题,从现在开始好好利用这两个月的时间制定合适的学习计划,也可以给自己的算法水平带来质的提升。

首先,为什么搞嵌入式底层开发还是要学算法和数据结构?

  虽然在搞嵌入式底层开发大多数数据结构用到的不多,学点常用的基本都能解决问题。例如,递归往往可以用于求解,其本质是从结果倒回输入的求解,常用于算法题,数据检索等;但不常见于嵌入式开发流程的场景应用,因为嵌入式往往是要从输入得到结果。但是我觉得还是有必要深入学习一下,这个不仅仅能够提升你代码的技术水平,还能提高你码代码的视界。

一、算法和数据结构的知识考点

算法和数据结构的关系

  如果把算法比作建筑工程的图纸,数据结构就像是建造大楼的工具。数据结构设计的初衷就是方便程序员使用,虽然看似种类较多,但实际上每一种都不难,可以结合算法一起学习。

二、探索卡片

  对于零基础的同学来说,不建议一开始就从题库页开始按顺序刷题。在力扣的探索页面有十分丰富的算法和数据结构主题卡片,从探索卡片开始学习能帮助你快速入门。每个卡片都覆盖了详细的知识点介绍,概念讲解,结构特点,代码实现,例题及答题套路。

  按照正确的顺序来刷探索卡片,由浅入深,逐层打好算法根基。

!

三、进阶

  按着上面的探索卡片学习;有了一定的算法和数据结构基础以后,这时你就可以选择刷面试题、或者题库了。

  要准备面试的话,多写写面试题;面试题可以选最近时期的「名企高频面试题」、「剑指 Offer」等。如果已经在准备面试冲刺的阶段,这时候不妨多刷两遍「剑指 Offer」题库。


  当然也可以养生刷刷题库;根据题库页的标签分类进行专项刷题也是一个非常不错的选择。

四、刷题技巧

  当我们开始刷一类算法题前,如果对此算法的概念还不太熟悉,花费 5 分钟左右的时间了解其概念是很有必要的。在力扣题库页的 标签分类 中,点击对应的标签即可查看算法概念。

  在足够多的准备工作后,我们就可以开始找一道简单~中等的题目小试牛刀了。有的同学会想:直接从困难题目开始练习,练会了困难题目,再去看简单题和中等题岂不是轻而易举?事实上我们不建议初学者直接练习困难题目。因为困难题目往往不够典型,困难题总是糅合了多种算法,难点在于对多种算法的综合应用,不适合在学习阶段用来专攻某一类算法。


  下面举一个具体的例子,比如我们计划本周刷深度优先搜索的题目。先点击题库页「深度优先搜索」标签,查看其概念:

  从概念中我们知道,深度优先搜索,简称 DFS,主要用于遍历或搜索树或图。核心是沿着树的深度遍历树的节点,以深度优先的方式来遍历一棵树,直到找到需要搜索的节点或是遍历结束。

这不难理解,了解完概念,我们的脑中就对此算法有了一个粗略地认识:

  • 想象我们正站在一棵大树前,我们想要浏览这棵树的整个结构。
  • 于是我们选择从大树的根出发,往树枝处浏览;
  • 遇到树木分叉的地方,就随机选择一个树枝开始浏览;
  • 浏览完后,回到上一个分叉的地方,选择另一个树枝继续浏览,直到所有的树枝都浏览完成。

  事实上,深度优先搜索和树形结构经常成双成对出现,二者总是密不可分。有了一个粗略的认识后,我们应该立即选择一道简单的题目开始练习:

看到题目,我们的第一想法可能是以根节点为中心,左边的最长路径加上右边的最长路径应该就是答案。如题目示例中的树:

根节点左边的最长路径为 2,右边的最长路径为 1,所以和为 3。

看起来没有错,我们再考虑一些特殊情况,有没有可能最长路径不经过根节点呢?不妨画个草图看一下:

对于这样一棵树,根节点没有右子树,所以根节点右边的最长路径为 0,而左边的最长路径是 3,所以这样算起来直径为 3。但我们发现以2做为根节点的子树直径为 4,大于我们当前算法算出的直径!显然我们之前的思路是错误的,根节点其实不一定经过根节点,子节点可能存在更长的直径。我们不得不选择另一种思路。

如果此时冥思苦想,仍然没有思路的话,我们可以点开题解区抄一下别人的解题思路。先依着葫芦画瓢,等学会了再自己创造。

我们看到本题题解区有力扣官方发布的题解:

  看完题解我们已经有了具体的解题思路。此时切记不要眼高手低,不要觉得看懂了就是会了,一定要亲自将代码敲一遍,有过刷题经验的人都知道,看别人解题和自己亲自上手是完全不一样的感觉。经常是脑子和眼睛在说:我会了。而手在说:不,你不会!

仿照着官方题解,我们写出本题的 kotlin 解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
var ans = 0
fun diameterOfBinaryTree(root: TreeNode?): Int {
ans = 1
depth(root)
return ans - 1
}

fun depth(node: TreeNode?): Int {
if (node == null) return 0 // 访问到空节点了,返回0
val L = depth(node.left) // 左儿子为根的子树的深度
val R = depth(node.right) // 右儿子为根的子树的深度
ans = Math.max(ans, L + R + 1) // 计算d_node即L+R+1 并更新ans
return Math.max(L, R) + 1 // 返回该节点为根的子树的深度
}
}

  这是一道非常典型的 DFS 算法题,刷完之后我们应该反复思索,做出总结:DFS 的核心是依次尝试,运用的主要手段是递归函数。

然后我们马上再找一道近似的题,继续练习本类算法,比如:

  这道题与上道题非常类似,它也是非常典型的 DFS 题,因为它没有掺杂多类算法,实际难度算不上困难。这一次我们争取不查看题解,先将上题的模板拷贝过来,加以修改写出解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
var max = Int.MIN_VALUE

fun maxPathSum(root: TreeNode?): Int {
maxDeep(root)
return max
}

fun maxDeep(node: TreeNode?): Int {
if (node == null) return 0
val L = Math.max(maxDeep(node.left), 0)
val R = Math.max(maxDeep(node.right), 0)
max = Math.max(max, node.`val` + L + R)
return node.`val` + Math.max(L, R)
}
}

如果此时仍然不能手打出一道完整的典型 DFS 题目,就继续反复练习,坚持这个过程,直至自己完全掌握此类题目。

总而言之,算法学习技巧可总结为四个步骤:一看二抄三改四写。

  • 一看:先查看基本概念,知道这类算法是什么。
  • 二抄:照着别人的解题思路,将代码完整敲一遍,理解其思路。学习算法切忌自己造轮子,绝大多数问题都早已经有了完善的解决方案。
  • 三改:拷贝自己以前敲的模板代码,加以修改,反复巩固。
  • 四写:看答案与改答案 AC 的题不能算是真的会了,必须自己能手打出完整的代码才是真正会了。

五、时间规划

  梳理完算法学习的先后顺序和刷题技巧,一份可执行的时间计划是非常重要的,大家可以根据自己的学习进度安排,下面列出一些计划的要点。

5.1 确定学习方式

  有的同学基础还比较薄弱,就需要花一定的时间梳理知识点,可以通过探索卡片或者看书学习,在刷题前至少保证一周左右的时间充分梳理知识点,而基础比较扎实的同学可以适当缩短梳理知识点的时间,或者直接从题目开始刷。

5.2 计划刷题总数量

  一般来说,刷 150 - 200 题就能比较充分地应对技术面试了。同学们可以根据时间按照实际情况调整。在这个基础上可以预估每天要花多少时间刷题,刷多少题。

5.3 预留面试前复习时间

  复习是刷题过程中非常重要的一个环节,刷了一定数量的题目后,可以准备一周的时间系统回顾错题和难题,避免出现面试时遇到做过的题仍然回答不上来的情况。

5.4 安排实战演练和冲刺时间

  在正式开始面试前的一到两周,你就需要进行大量实战演练和冲刺刷题了,在这个阶段反复练习 70+ 道2020 年互联网名企高频面试题探索卡片,保持刷题的手感。

-------------本文结束感谢您的阅读-------------