LeetCode 纯 C 二周目刷后感

上次发了一篇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