V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
begeekmyfriend
V2EX  ›  LeetCode

LeetCode 纯 C 二周目刷后感

  •  6
     
  •   begeekmyfriend ·
    begeekmyfriend · 2018-01-11 16:52:35 +08:00 · 8982 次点击
    这是一个创建于 2268 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    第 1 条附言  ·  2018-01-11 17:40:01 +08:00

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

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

    来一波广告,AC 480+: https://github.com/liupangzi/codekata
    begeekmyfriend
        12
    begeekmyfriend  
    OP
       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
        13
    etins  
       2018-01-11 23:10:23 +08:00
    上一次见你还是在知乎上,666
    p64381
        14
    p64381  
       2018-01-12 09:40:33 +08:00 via Android
    指针不就是结构体类型指针、char*、void* 这几种么,原始指针是什么
    p64381
        15
    p64381  
       2018-01-12 09:59:17 +08:00 via Android
    原来你是说 container_of
    begeekmyfriend
        16
    begeekmyfriend  
    OP
       2018-01-12 10:08:29 +08:00
    @p64381 我指的是 next、prev 这些,可以封装的
    xingqiuditu
        17
    xingqiuditu  
       2018-01-12 11:22:45 +08:00
    @begeekmyfriend 楼主很厉害,可以顺便分享一下 medium 和 hard 难度 10 到 20 道你刷的时候感觉比较经典的题目吗
    begeekmyfriend
        18
    begeekmyfriend  
    OP
       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
        19
    xingqiuditu  
       2018-01-12 13:40:12 +08:00
    supercaizehua
        20
    supercaizehua  
       2018-01-13 12:47:58 +08:00 via Android
    大佬,寒假想研究学习您的代码,然后可以把我自己的分析贴在我的博客吗
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1061 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 22:41 · PVG 06:41 · LAX 15:41 · JFK 18:41
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.