登录
  • #刷题
  • #leetcode

跳出‌‌‌‍‌‌‍‌‍‌‌‍‌‌‌‌‌‌‍‍‍‌‍‌‌‌‌‍‍‍‍‌刷题的自我怀疑

WIwindson
4889
22
刚接触 Leetcode 的时候,我经常边刷题边陷入自我怀疑,通常有几个原因:1)想不到最优解:一些简单题目的最优解,我觉得自己不可能想出来,也不太能理解。2)看不懂解法:论坛中被赞最多的解法往往为了追求代码的简短性而忽略可读性,在刷题初期要理解解法都需要耗费大量时间。3)差距太大:网上有不少,他们在 20 分钟之内就能解答四道题目,对比之下,实在自愧弗如。

这几个原因导致的自我怀疑不仅打压了我刷题的热情,耗费了大量时间,也影响了我对自己真实算法水平的判断。如今刷过一些题之后,我开始了解到一些更深层的原因,希望在此能帮助到刷题中迷茫的各位:

简单题不简单

我推测 Leetcode 的题目难度并不是根据最优解的难度来设定的,也就是说一道标记为简单的题目它的次优解可能非常直观,但是最优解却很难想出来。这一点对于当初是刷题新手的我尤其致命,因为在被最优解的美妙所震撼之后,我强迫自己理解和证明它,但是如果在一定时间内还没有成功,我就会陷入深深的自我怀疑,举几道题目为例:

最大子序和(简单)

官方解答轻描淡写地给出了分治解法以及动态规划解法。这两个解法容易想到吗?《编程珠玑》第八章讨论了这个问题:

“... 1977年的时候,他将该问题叙述给 Michael Shamos 听,结果 Shamos 花一个通宵就设计出了算法3(注:分治解法)。过了没多久,Shamos 向我介绍这个问题,我们一致认为这很可能是最好的算法了,因为研究人员刚刚证明了几个类似的问题需要正比于 O(nlogn) 的时间。几天之后,Shamos 在卡内基—梅隆大学研讨会上介绍了该问题及其历史,结果与会的统计学家 Jay Kadane 在一分钟之内就勾勒出了算法4(注:动态规划解法)。好在我们知道不会有更快的算法了:任何正确的算法都必须至少花费 O(n) 的时间“
数学家 Michael Shamos ,花费一个通宵才设计出分治解法。而且他和计算机科学家 Jon Bentley 都没有想到动态规划最优解,我又何必要求自己在两个小时内想到。

环形链表(简单)

最优解使用了 Floyd 判圈算法,一般来说,算法带人名的都不是凡夫俗子可以想到的。

多数元素(简单)

最优解使用了 Boyer-Moore 投票算法,它的一般形式发表了一篇论文,具体可以浏览这里的介绍

寻找重复数(中等)

最优解是 O(N) 的快慢指针解法,我当初看到这个解法的时候感觉难以置信,不禁让我去查找这个解法的相关资料,最终找到了这篇文章

“This problem (reportedly) took CS legend Don Knuth twenty-four hours to solve and I have only met one person (Keith Amling) who could solve it in less time than this.“
Don Knuth ,算法界的传奇,著作包括《计算机程序设计艺术》这本巨著,花了 24 小时想到快慢指针的解法。

这样的例子还有不少,我举这些例子并不是让你自我安慰或满足于次优解。而是说某些题目的最优解是很难想出来的,了解这些事实才可以对自己的水平进行更加准确地评估,不会因为花一个小时想不出最优解而自怨自哀。另外,做题过程中若被题目的难度标签所影响,高估或者低估自己的真实水平都对于面试并没有任何帮助,所以我现在都使用自己开发的 Leetcode invisible 插件隐藏了题目的难度。我建议 Leetcode 可以参考 Google Kickstart 进行分级,一道题目可以分两个难度标签和两个测试集,例如,最大子序和这道题目的标签是 简单 | 困难,代表次优解比较简单,但是最优解需要一些巧思才能解决。

熟能生巧

我在 Leetcode 大概刷了 800 题,熟悉了题目的套路之后,仅仅从题目名字就能推测到解法。例如 “石子游戏“ 一看就是 minmax 策略,“ XXX 子序列” 的话可以试试动态规划,“ XXX 最大的最小值” 是二分或者滑动窗口。但是这并不代表我的算法水平多么厉害,让我去做其他平台的题目我绝不可能从题目名字想到解法。同样地,竞赛的选手也有这样的优势,在做了大量题目,参加了大量竞赛之后,他们可以从题目名字或者描述中就能找到之前做过题目的影子,快速找到解法。

大神也会卡题

Lee215 是 Leetcode 美区 reputation 分数最高的用户,竞赛成绩也很前,一些题解更是令我醍醐灌顶。cuiaoxiang 是 Leetcode 国区竞赛前列,经常在 20 分钟能解答四道题目。但是即使优秀如他们,偶尔也会遇到卡题的情况,推荐这个 Lee215 第一人称解说的竞赛视频,。可见,算法涉及的东西非常多,大家熟悉的领域也不同,即使我在 30 分钟内解答了那道题,也绝不代表我比 cuiaoxiang 厉害。

竞赛不是面试

大部分人刷题都是为了面试而不是竞赛,而面试和竞赛其实差别很大,竞赛选手沟通不一定强,面试选手竞赛不一定厉害。竞赛的时候题目会给定所有限制条件,只需要写代码提交,不需要向其他人解释自己的思路。但是面试需要让面试官理解自己的思路和代码,也可以让面试官提供一些帮助,对于沟通的要求要更高。

总结

刷题离不开坚持和努力,更需要保证良好的心态,我在刷题初期的时候,经常会心态崩溃。现在回过头看,实在是没有必要,最后分享一句话给大家,共勉。

"If you are not enjoy it, you are doing it wrong."

©海外兔版权所有,请勿转载
22条回复
热度排序

发表回复