刷算法题时如何评估和提升自己的能力?

2023-07-25 19:27发布

计算机行业细分下来领域其实很多,系统、网络、硬件、前后端、算法等等。但是不管我们处于哪个细分领域,找工作第一件事就是刷题。算法题也是面试中让很多人头疼的部分,主

计算机行业细分下来领域其实很多,系统、网络、硬件、前后端、算法等等。但是不管我们处于哪个细分领域,找工作第一件事就是刷题。算法题也是面试中让很多人头疼的部分,主
1条回答
佀国旗
2023-07-25 20:18 .采纳回答

计算机行业细分下来领域其实很多,系统、网络、硬件、前后端、算法等等。但是不管我们处于哪个细分领域,找工作第一件事就是刷题。算法题也是面试中让很多人头疼的部分,主要难点有两个:

知识点类别多。算法题涉及到的知识点非常广泛,比如数组,链表,树,图,排序,贪心等等。

知识点难度大。除了类别多之外,有些题目也特别难,代表就是力扣中众多的 Hard 难度的题目。

除此以外,还有一种情况是有的时候明明已经刷了很多题了,但是面试的时候还是脑子一片空白,对一些相似题型做不到举一反三。这说明刷题也不是盲目无脑平推就行,除了讲量,还要讲方法。尤其是对算法相关知识不是特别熟练的同学,掌握一些好的刷题策略是非常重要的。我们先来聊一聊学习算法的一些策略和常见误区。

一、AC 只是开始

应该如何判断自己的实力呢?相信大家都在力扣上得到过很多的 Accept,也就是 AC。假如来了一道题,可以假想这是面试官给的题目,我们这里可以简单地将解答分为四个级别:

  • 第一个级别,我们磕磕绊绊或者靠着面试官的提示写出了正确的解法;
  • 第二个级别,我们快速写出了正确的解法,能够完美应对所有的测试数据,包括可能的边角数据(Corner Case);
  • 第三个级别,我们快速写出了正确的解法,并且写出来的是最优解法,一般题目对于时间复杂度考察比较多,这里默认是最优的时间复杂度;
  • 第四个级别,我们的代码风格非常优美,变量名含义清晰,过程清楚明白,有一些简单的注释。

有时候我们可能发现面试的时候明明都写对了,最后还是没通过,这就有可能是你的代码风格没有让面试官满意。所以,在平时刷题的时候,我们也需要注意这几个方面的内容,而不是看到 AC 就不管了。千万牢记,AC 只是开始。

二、规划刷题过程

力扣上大概有快 2000 题了,但是大部分人备考算法的时间可能只有 2 个月左右。在这么短的时间内要刷完所有题并且掌握是很困难的,实际上也不是非常必要。力扣的题目有难度区分,不同力扣题的定位是不一样的。甚至在不同的人看来,作用也是不一样的,对于不同的人,刷题的策略也应该有所区别。

小知识:力扣的题目越往前越经典,相对来说被考查的概率也越高。

算法新手

首先,如果我们是刚接触算法题目,这时可以按照不同的专题分专题来刷题,比如动态规划专题,栈专题等等。我们需要尽量吃透每一个专题的内容。量的话可以每一个专题完成 60% Easy 的题目,选择并完成大概 30% 左右的 Medium 题目,Hard 题目的话可以挑少量进行尝试,不过不用苛求。在这个阶段,刷题的重心在于确保自己理解每道题的解法,并能独立快速正确地写出代码。

有一定算法积累

然后,如果我们对算法比较熟悉,或者已经完成了第一个阶段,这时就需要大量地综合巩固我们的知识脉络和手感。这个阶段也就是我们说的「无脑刷题」阶段。不过刷题也并不是完全无脑,题目我们可以按顺序刷也可以随机刷,但是一定要注意这个阶段的重心是不一样的,我们要确保每道题的解法都是最优的,并且确保快速。这里可以给一个简单的标准:对于大多数 Easy 题,从读题到 AC 不超过 8 分钟;对于 Medium 题,从读题到 AC 不超过 30 分钟(时间仅供参考,不过相信自己,实际上你可以做到比这个快很多)。如果有余力,我们可以进一步注意我们的代码风格,如变量命名、易读性等问题。刷题方式是建议每天先不停地刷 Easy,注意保持 AC 节奏和速度。然后最后做几道 Medium 收尾。

能轻松解决 Easy 和 Medium

最后,如果前面的部分已经完成得很好了,剩下的就是继续拔高的过程。这里主要是两个方向:一个是难题和新知识点,我们可以接触一些高级的算法和数据结构,如线段树、矩阵乘法、网络流、代码量大的模拟题等。

小技巧:在做题的过程中,我们也需要思考题目可能的变形和扩展。这个主要推荐在第一和第三阶段做,第二阶段主要还是训练速度和准确率。一方面,在实际面试过程中经常会碰到原题被包装了一下,或者稍微进行了改动;另一方面,这也是对自己很好的锻炼和拔高,这个过程对于新手还比较困难。因此,课程也会提供题目的不同变形和扩展,从易到难不等,帮助大家建立举一反三的好习惯。

三、算法进阶

​在有了一定的算法基础以后,可以提升一下应试能力,主要是在高压下的做题能力,这里推荐力扣每周举办的周赛和每两周举办的双周赛,比赛持续一个半小时,时间一般为每周日的早上 10:30 开始或者是周六晚上 22:30 开始。题目全部为之前未出现过的新题,一般前两题不涉及具体算法或涉及一些简单的算法思想,后两题则可能考察各方面的算法能力。简单来说,相比于自己刷题,参加周赛有以下几点显而易见的区别或者优势:

  1. 检验算法能力: 不同于自由刷题的轻松环境,现在需要在一个半小时内 AC 四道题目,这无疑对我们的算法思维敏捷、清晰程度,以及代码能力(包括速度和准确性)都有了很高的要求。磕磕绊绊地 AC 题目,虽然可以满足平时的刷题需求,但是实际上是满足不了周赛,或者说实际面试时的要求的。
    根据每次周赛的名次,以及 AC 题目的数量,我们可以粗略地量化我们的算法实力。这样能直观的发觉这段时间的训练是否有带来提升,或者还有哪些不足的知识点和内容需要补充。
  2. 增加抗压能力: 限时和比赛的另一个好处是能营造一种紧张的氛围,帮助我们集中注意力。虽然比不上正式面试的环境,但也是一种良好的过渡。在经历了多次比赛的洗礼后,再碰到类似的情景(例如笔试),我们能够有更加良好的心态来面对。
新人入赛周赛排名规则

如果你是一名竞赛新人,我们不妨打开最新的一场周赛排名,然后一起来了解一下周赛的具体排名规则。

一场周赛最多可能有近万人报名,但是题目只有四道,如何对选手进行排名呢?这里主要是通过三个方面来进行的。

  1. 题目积分。 根据难易程度,不同的题目有不同的分数,每通过一道题目均能得到相应的题目分数。当两个选手分数不一致时,分数高(即过的题多)的选手显然名次更靠前。
  2. 时间。 同样的题目,在两个人都通过的情况下,一个人用时 10 分钟,另一个人用时 1 小时,显然也是用时短的更优。因此,在分数一致的情况下,通过最后一题时间更靠前的选手,排名更靠前。
  3. 错误次数。 由于写代码不可避免地会碰到出 bug 的情况,相同条件下显然出 bug 次数少甚至没有 bug 的选手是更厉害的,即代码能力更强。为了量化代码准确度,每出现一次错误的提交(包括但不限于答案错误,内存超限,时间超限等等),如果后续题目通过了,之前的每次错误提交均会在最终通过时间上增加 5 分钟的惩罚。

正是由于错误惩罚机制,大家在提交答案之前一定要仔细检查,避免不必要的罚时。

周赛爆 0 怎么办?

如果大家是第一次参加周赛,那么只做出来一道题甚至一道题都没做出来都是很正常的。例如下列常见场景:

  1. 题目似乎简单,但是脑子里想法错了导致实现一直出问题。
  2. 看错题目问题,平白浪费时间。
  3. 复杂度计算错误,一直超时。
    ...

以上任何一个场景都可能会导致我们周赛成绩不佳,甚至 0 题通过。实际上类似”脑子短路”的问题在平时刷题的时候我们可能也会出现,但是那时基本很难意识到这些情况的发生,因为我们总是能求助各种题解和代码。而在限时压力的逼迫下,这些小问题的影响就会逐渐放大,导致我们发挥不出应有的水平。所以一方面我们需要不断参赛锻炼自己的心理素质,另一方面就算某次成绩不佳我们也不需要因此自责,只需要反过来思考这场比赛中发现的问题即可,例如:

  1. 是否有漏掉没掌握的知识点?
  2. 是否某些题目思路想的过于复杂,增加了实现难度?
  3. 是否当时太紧张导致思路不清晰?
  4. 是否某些题目其实还没想清楚就着急动手实现了?
    ...

通过一次次的参赛和总结,我们终究能锻炼出一个良好的应试状态,并且对常见知识点信手拈来。

周赛难度

周赛一共有四道题目,分别对应的难度是:

  1. 基本不涉及任何算法,只是考察代码实现,几乎无难度。
  2. 考察一些简单的代码知识。
  3. 考察某类算法,题目一般较难。
  4. 考察某类算法,或者综合考察一系列算法。算法可能 超纲,题目难度浮动很大,最简单的可能是 medium 略高难度,最难的可能远超普通 hard 题目。

一般如果大家完成了数据结构部分的训练,对于周赛的前两题压力应该是不大的,某些情况下第三题也可以轻松地解出来。如果是系统地完成了算法学习的同学,顺利的情况能够完成前三道题目。对于第四道题目,在有余力的情况下也可以尽量尝试,某些题目简单的场次还是能够做出来的。小知识:第四题之所以难度浮动会大,是因为力扣实际上没有 hard 以上的难度评级,这就导致了力扣的题目只要比 medium 难都会归为 hard 难度。因此 hard 难度反而是最难区分的难度范畴。包括大家刷题时,可能觉得有的 hard 很简单, 有的 hard 很困难,也是这个原因。

周赛名次

如果能够顺利通过前两题,基本能稳定拿到 1000 ~ 2000 名左右的名次。如果进一步能通过三道题目,排名会来到 100 ~ 1000。发现了什么没有?前三题都能有 1000 人通过,但是通过四题的人一场可能也就一两百人,这也是为什么说不用对第四题进行苛求。至于前 100 名的位置,基本都是通过四题的人了,这时比较的就是通过时间和罚时,甚至于前 10 的人很多能在 20 分钟以内完成四道题目,这对于我们可能是一个比较长期的目标了。

而短期的话,可行的路线是这样的:

  1. 尝试保证通过两道题目,排名 2000 以内。
  2. 快速正确通过两道题目,通过第三题,排名 500 - 1500。
  3. 死磕前三题,保证准确率(免罚时),保证实现速度,排名 100 - 200。
  4. 前三题稳定通过,尝试第四题,排名偶尔能进前 100。

在经过一段时间的训练,完成 1 和 2 压力还是不大的,但是到了 3 和 4 就需要付出更多的努力了。我们并不需要过分关注别人的成绩,例如前 10 名的人绝大部分都是 OI 或者 ACM 选手,很多人从高中起就开始刷题和训练了。只是针对面试和基础的话,我们并不需要到那种水平,多余的时间用来增加其他方面的专业技能会更有价值。

周赛小技巧

最后我们再针对一些常见技巧进行一些说明:

1. 关于程序的运行速度:算法运行的速度由两部分组成,一部分是算法复杂度,比如 O(n) ,另外部分是常量复杂度,比如 O(n) 也分到底跑了几遍 。在解题过程中,如果你发现你的程序运行速度慢,要注意区分是由于复杂度高,还是常数大。对于面试来说,只要你的算法复杂度是最优的,一般不会太介意常数大的情况,除非题目特殊要求。因此也不需要去针对别人 2ms,你 5ms,一定要优化那 3ms。

2. 关于空间复杂度,除非题目有特殊要求,一般不用太过苛求,不过你也需要知道一些基本的压缩空间的方法,例如如何用 O(m) 的空间写 01 背包。

3. 关于语言选择,不同的语言本身执行速度也是不一样的,都是正常的。因为很多题目并没有因为是 Python 所以合理地延长时限,导致有些题目正确的时间复杂度仍然有可能会超时,用 Python 需要注意。

4. 关于最优时间复杂度,有的题目可能不确定最优的时间复杂度是什么,比如看上去有一个 O(n^2) 的解,但是仔细优化可以有一个 O(n) 的解,但是不容易想到。在不能确定算法最优复杂度的时候,我们不妨看看数据范围。比如 n 是 10^6 ,那么 O(n^2) 的时间复杂度就是 O(10^{12}) 。经验上,我们可以认为计算机跑 10^8 复杂度的操作需要一秒。 那么 10^{12} 就需要 1000 秒,显然系统是不会给十几分钟用于单次评测的。那么反过来可以推断这个题的最优解是 O(n) 或者 O(nlog(n)) 。其他情况,如果 n 是 1000,那么就有可能是 O(n^2) ,如果 n 只有 20 以内,那么就考虑 O(2^n) 了。

本文内容选自:LeetBook《高频算法实战》

作者简介:小函,北京大学硕士。ACM/ICPC 亚洲区预选赛金牌,拥有大型算法竞赛命题经验。校招曾获得小米,阿里,头条,微软,百度,搜狐,快手等多家公司 offer,具有丰富的面试与被面试经验。在机器学习领域,曾获得多个国内外机器学习竞赛金牌和冠军。

内容简介:这门课程将帮助大家梳理面试中必须掌握的基础知识点,学习常用解题技巧,真正动手去 AC 每一个知识点。课程中还会讨论很多经典的算法题目,包括力扣题和小函老师亲自设计的题目,并对这些问题进行扩展发散,追踪知识点的原理,帮助大家知其然且知其所以然,而不只是记住解法。


本文作者:小函

声明:本文归 “力扣” 版权所有,未经授权不得以任何形式储存、转载或商用。

一周热门 更多>