力扣竞赛入门 – Road to Knight
本文最后更新于 132 天前,其中的信息可能已经有所发展或是发生改变。

经过这一两个月的学习,博主在恶补计算机基础理论的过程中,也在逐渐理解基础的算法,并参加到了 LeetCode 的日常竞赛中。

作为一个几乎从零开始的新手(鬼知道大学四年我干了什么),博主也是逐渐从基础分挣扎的“惨状”,一直到慢慢的提分,在某些情况下也开始得心应手起来。

虽然我们不能以过强的功利心去参与竞赛(在这种情况下很容易陷入厌倦),但是在竞赛的过程中,我们逐步投入并享受这个过程,势必能对个人的算法理解能力达成一定的提升。

在这里,我将分享一下,零基础的新人如何在 LeetCode 竞赛中寻求提升的路径,并达成一个短期可行的目标:竞赛积分达到 1900(Knight),并进入全球 10%。

(虽然这个分数和排名仍然有很大水分,毕竟 Knight 才算入门嘛)

基础规则

LeetCode 每次举行的竞赛中,主办方将会给出四道题目。

这四道题目难度与分数在大多数情况下是递增的(也有少数情况会有 T2 比 T3 难),分别为 简单 / 中等 / 中等 / 困难。做题顺序没有限制,需要在规定的一个半小时内作答。

比赛中除了编译错误(和 OJ 系统内部的错误)外,选手任何的 TLE(超时)和 WA(错误答案)都会在基础的解答时间内增加 5 min 的罚时,在选手第一次提交成功答案后计算。

所有题目的总解题时间按各题目中最慢者计算。

这里举几个例子:

  • A 选手在解答 T1 时出现了一次编译错误,网络出现两次丢包等问题没能成功提交,又有一次 TLE 和两次 WA,最终给出答案在比赛开始后 7 min 30 s:
    解答时间为 :7 min 30 s + 5 min * 2(WA)+ 5 min (TLE)= 22 min 30 s
  • B 选手在 T1 和 T2 结束后,计算罚时后解答时间分别为 15 min 和 12 min,T3 出现两次 WA,后续未成功提交正确答案:
    解答时间为:T1 耗时 15 min,因其解答时间更晚。计分为 T1 + T2 分值。T3 因为没有正确解答而不罚分。

比赛的排名以分数优先,分数相同时以答题时间优先。

基础中的基础:模拟(T1)

首先说到第一题,一般这一题的数据范围不大,不需要优化算法也几乎不会有 TLE 的问题。

这个部分考察的内容一般只会有:

  • 基础的语言语法内容,包括运算符/条件循环,少数情况也会有位运算的内容。
  • 对题目逻辑的理解,暴力模拟排除即可。

一句话总结就是:看得懂字,有手就行。

牛刀小试:模拟 / 基础算法(T2)

来到第二题之后,也算是迈入了第一个开始考量算法基础的关卡。

一般这道题的数据范围会在 10 ^ 5 左右。虽然也不会太大,但大多数情况下,不能使用类似于时间复杂度 O(n^3) 这种过于暴力的解法。

这个部分考察的内容大致为:

  • 算法:双指针 / 二分查找 / 哈希表 / 矩阵。(大多数情况)
  • 数据结构:数组 / 矩阵 / 单链表。(大多数情况)
  • 基础的条件判断,排除不符合的答案。(少量出现在较难的逻辑题目)
  • 有时熟练运用编程语言现有的库和函数(轮子)可以事半功倍。(例如 strconv.Atoi,sort.Slice 等)

这部分内容只需掌握基础的算法和数据结构知识,还有对所用编程语言的基础库使用。

一般来说,能快速完成前两题的情况下,新人选手将能很快的达到1700+。

新手之壁:进阶算法知识(T3)

来到第三题,一般来说这一题会比之前更困难。

其数据范围会相比之前更大(往往会达到 10 ^ 9),也需要利用好更多进阶的内容。

这个部分考察的内容大致为:

  • 进阶算法:动态规划 / 滑动窗口 / 贪心算法 / 单调栈 / DFS / BFS 等。
  • 数据结构:数组 / 矩阵 / (更复杂的)链表 / 二叉树 等。
  • 同样的,熟练运用编程语言现有的库和函数(轮子)可以事半功倍。

这一部分开始真正展示算法的精妙之处,也是很多相关专业大学生会接触到的范围。

能否成功解答第三题,这是新手冲击 1800+ 的关键所在。

而能否快速的解答第三题,这是稍微熟练的选手冲击 Knight 段位的关键。若能经常的在 30 min 内不出错的解决前三题,选手将更有可能冲击 1900+,也就是当前 Knight 的分数线。

真正的试炼场:高级算法与数据结构(T4)

也许看到这里,有些 ACM 选手要嗤之以鼻了:“就这?这些题在 ACM 赛场上都不够塞牙缝的。。。”

虽然 LeetCode 的竞赛难度,对于真正修仙的算法竞赛者自然不够看,但我们这里讨论的是普通学习者和大部分从业者的状况。

对于这大部分人群来说,T4 所涉及的算法内容,已经算是在基础之上的探索与试炼了。

这个部分考察的内容一般会有:

  • 高级算法:多维的动态规划 / 字典树 / 分治 / 回溯 / 剪枝 等。
  • 数据结构:多叉树 / 有向图 / 散列表 等。

这一部分对于新手来说几乎遥不可及,但这也是在算法方面走向精通的必经之路。

同样的,若能成功解决T4,选手将很有可能拿下 LeetCode 平台当前的最高段位 —— Guardian。

至于快速的解决 T4,这就是头部大佬或者 ACM 骨骼精奇选手的事情了,若有兴趣就继续前进吧!

总结

参与到 LeetCode 这样的入门算法竞赛中,我们应当摒弃功利心,以学习和探索的心态走向计算机算法的世界中,在参加比赛的过程中不断理解新知识提升自我。

也希望看到这篇文章的各位,若能参与到竞赛中,可以一起学习,一同进步。

本站作品采用 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 进行许可。

评论

  1. Macintosh Chrome
    3 月前
    2024-1-23 0:01:10

    以我的资质可能一题都做不了就被刷了!!

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇