LeetCode 纯 C 二周目刷后感

[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

吐槽一下（单）链表题。虽说（单）链表是C语言的标配，也是各大公司题库里的常备军。但对于我这个C语言程序员来说，单链表真的过时了。熟悉我代码的人都知道，我是用list head循环双链表来解决问题的，我从来不用单链表（LeetCode二周目刷题我唯一懒得再刷而放过的类型）。单链表容易玩出花活，特别是玩指针——翻转、相交、复制拷贝等——本质上是由于数据结构本身的单薄引起的，这些花活放在list head下基本没啥可玩性了，因为list head本身优良设计就把这些技巧解决了。这也使我懒得再去碰单链表。有人说单链表省了一个指针，对于嵌入式设备这周内存受限场景适用。但是list head是内核源码，嵌入式内核都不怕，我们又何必为了节约几个字节而去写出暴露原始指针的C代码呢？我是不鼓励在C里面玩raw pointer的，我甚至认为训练有素的C程序员应该掌握尽量避免适用原始指针的技术。最后，如果一个公司给你出的面试题里有单链表，我奉劝你慎重考虑，估计他家代码属于那种不太好维护的写法。

[Immortal]

学到不少,佩服楼主

[0915240]

上一次 61 天前 这次都二刷了 牛逼

[leeZoom]

膜拜大佬…学习了

[chenqh]

不过感觉 leetcode 跑时不准呀

[sfqtsh]

// TODO: fork your repo and then add a README with question description to each subfolder.

[ballshapesdsd]

看到楼主 id 想到李小龙的话，be water my friend

[begeekmyfriend]

@ballshapesdsd That's it!

[congeec]

你那个链接 404 了

[begeekmyfriend]

@congeec 这不好好的？ https://www.v2ex.com/t/405467

[congeec]

@congeec
leetcode 的那个：word ladder II
https://leetcode.com/submissions/detail/127189827

[holyghost]

是这样的，但是一般我都是争取一遍最优，如果不是就直到自己想出来为止。
缺点是进度非常慢

来一波广告，AC 480+： https://github.com/liupangzi/codekata

[begeekmyfriend]

@congeec 看来我疏忽了，除了我，别的账号看不到。你还是用我的 github 代码提交查看吧： https://github.com/begeekmyfriend/leetcode/blob/master/126_word_ladder_ii/word_ladder.c

[etins]

上一次见你还是在知乎上，666

[p64381]

指针不就是结构体类型指针、char*、void* 这几种么，原始指针是什么

[p64381]

原来你是说 container_of

[begeekmyfriend]

@p64381 我指的是 next、prev 这些，可以封装的

[xingqiuditu]

@begeekmyfriend 楼主很厉害，可以顺便分享一下 medium 和 hard 难度 10 到 20 道你刷的时候感觉比较经典的题目吗

[begeekmyfriend]

@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]

@begeekmyfriend 谢谢

[supercaizehua]

大佬，寒假想研究学习您的代码，然后可以把我自己的分析贴在我的博客吗