LeetCode 纯 C 二周目刷后感

2018-01-11 16:52:35 +08:00
 begeekmyfriend

上次发了一篇C 语言刷 150 道 LeetCode 经验谈,这次刷了二周目,把题量增加到 200 道。再写一点感想。

为啥要刷第二遍?这是跟一个硅谷回来的计算机大牛交流过的缘故,他当过面试官,但我们不是在面试。他跟我说,你刷了这么多题,已经比大部分人都优秀了。但其实没必要刷这么多的数量,你挑出几道典型的题目,但需要都做到最优,就足够了。这也是我刷第二遍的动机,第二遍的目的不是为了记忆,而是再看看写过的代码有没有提高空间,这是我在第一遍时没有特别注意的地方。于是我又花了近一个月的时间,再提交了一遍,把排名在最前方的直方图上推荐的代码参考了一遍。

刷第二遍是否值得?我认为值得。首先,我发现 LeetCode 的测试用例在更新,以前 Accept 的答案,到第二遍时又 fail 了,但大部分都是加了点边界条件等小 case,补一下即可。不过也有的可能加上了 case 的量,导致你直接拷贝最佳参考都无法达到前排了;其次,别人的代码比你更精简,第一遍怎么过怎么来,回过头来看,很多逻辑写得过于繁琐了,别人的逻辑就是比你清晰简明,那么就毫不犹豫地替换吧;最后,你仍旧存在爆机的几率,我看到有意思的地方在于,有几道题,最新的参考答案里借鉴了我的写法,爆了我的机。还有几题,我借鉴了参考答案的思路,再换成自己的写法,又爆了别人的机。看来通过开源的互补,我们都各自上了一层楼。

其实很多题不存在绝对的最优写法。虽说我是奔着最优解去刷第二遍的,但大多数题目——哪怕存在最优算法——却并不存在最优写法的,这不是说 benchmark 持平的问题,而是 LeetCode 平台计算 benchmark 的时候存在随机性,个人猜测可能某一次(甚至好几次)提交,恰巧处于服务器繁忙时刻,一直跟最佳参考差了几个毫秒,搞得我很郁闷。但过几天,再提交一次却发现 100%爆机了。所以话说回来,并没有严格的方法证明某个写法是最优的,benchmark 排名有一定运气成份。

学习算法是否靠记忆?我的答案是,记忆是必要的,但是——不要记代码,不要记代码,不要记代码!我们需要记忆的是数据结构的状态动图,脑海中能够从当前假想的一个状态切换到下一个状态,最终达到目标,那么可以说这个算法你记住了。比如反转单链表,12345、21345、32145 ……移植到 54321,记住这个就行了,代码自然会写出来。如果光凭记代码,到了面试现场很可能会出错,而且你还不知道怎么写正确。

为了性能,能调用库函数的尽量用库函数写。比如排序,C 可以直接用 qsort,以前我也勤劳地手写过,不过直接 qsort 会让你的 benchmark 进一步提高。

为了精简,尽量用现成的数据结构,避免使用原始指针,避免使用原始指针,避免使用原始指针!比如 list.h 里面就提供了循环双联表和哈希链表的最佳实践,取自内核源代码,实用性和性能都是属于久经考验的写法,应该属于 C 语言必知必会,能用就用吧。我都靠着这几招刷爆了 10 道左右的老题了,也许用 C 去跟 C++/Java 这种自带轮子的高级语言比解题就靠这个了,我至今还清楚地记得word ladder II这道题 C 语言记录里收录的就是我的写法,比第二那种原始指针写法快了 60ms。另外我不喜欢平台推荐的 uthash 这种库,我讨厌宏,而且用它的几乎不出现在最佳参考里。

内存管理方面,不要直接用 realloc 我以前说过。还有不要 malloc 大块,平台 runtime 不支持。比如我想分配一个二维表,我喜欢的写法是先 malloc 一个连续一维大块,再用一个二维指针数组去引用它,这样内存的利用有局部性优势。很可惜 LeetCode 平台会出错,你不得不 malloc 很多小块才能通过。

请把命名写好。虽说刷题的代码没必要很严谨,也不必要具有美感,但是为了造福后来者,把代码写得易读性高绝对属于公益。我就花了一个多小时为了看懂某个题里最佳参考是什么思路,要不是有一点算法基础,参考答案里 ABC 命名法搞得我都快放弃了,还好最终我用自己改进的写法刷爆了这个恼人的参考,不知 LeetCode 后来有没有收录我的答案;-P

9030 次点击
所在节点    LeetCode
20 条回复
Immortal
2018-01-11 17:08:45 +08:00
学到不少,佩服楼主
0915240
2018-01-11 17:09:49 +08:00
上一次 61 天前 这次都二刷了 牛逼
leeZoom
2018-01-11 17:12:33 +08:00
膜拜大佬…学习了
chenqh
2018-01-11 17:14:28 +08:00
不过感觉 leetcode 跑时不准呀
sfqtsh
2018-01-11 17:19:56 +08:00
// TODO: fork your repo and then add a README with question description to each subfolder.
ballshapesdsd
2018-01-11 17:41:04 +08:00
看到楼主 id 想到李小龙的话,be water my friend
begeekmyfriend
2018-01-11 17:46:45 +08:00
@ballshapesdsd That's it!
congeec
2018-01-11 17:48:57 +08:00
你那个链接 404 了
begeekmyfriend
2018-01-11 17:50:33 +08:00
congeec
2018-01-11 18:17:52 +08:00
holyghost
2018-01-11 18:23:59 +08:00
是这样的,但是一般我都是争取一遍最优,如果不是就直到自己想出来为止。
缺点是进度非常慢

来一波广告,AC 480+: https://github.com/liupangzi/codekata
begeekmyfriend
2018-01-11 18:27:26 +08:00
@congeec 看来我疏忽了,除了我,别的账号看不到。你还是用我的 github 代码提交查看吧: https://github.com/begeekmyfriend/leetcode/blob/master/126_word_ladder_ii/word_ladder.c
etins
2018-01-11 23:10:23 +08:00
上一次见你还是在知乎上,666
p64381
2018-01-12 09:40:33 +08:00
指针不就是结构体类型指针、char*、void* 这几种么,原始指针是什么
p64381
2018-01-12 09:59:17 +08:00
原来你是说 container_of
begeekmyfriend
2018-01-12 10:08:29 +08:00
@p64381 我指的是 next、prev 这些,可以封装的
xingqiuditu
2018-01-12 11:22:45 +08:00
@begeekmyfriend 楼主很厉害,可以顺便分享一下 medium 和 hard 难度 10 到 20 道你刷的时候感觉比较经典的题目吗
begeekmyfriend
2018-01-12 12:30:44 +08:00
@xingqiuditu 以基础性、实用性和趣味性为准,挂一漏万:34、39~40、50、46~47、60、72、76~78、84~85、90、98、102、105~106、124、135、144~146、164、198、207~208、229、235~236、239
另外,我觉得很多 easy 的题很适合面试,代码量短,时间有限,你不说我就不列了
xingqiuditu
2018-01-12 13:40:12 +08:00
supercaizehua
2018-01-13 12:47:58 +08:00
大佬,寒假想研究学习您的代码,然后可以把我自己的分析贴在我的博客吗

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/422083

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX