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

leetcode 刷题有感

  •  
  •   cloudzhou · 2014-10-08 14:02:32 +08:00 · 13944 次点击
    这是一个创建于 3459 天前的主题,其中的信息可能已经有所发展或是发生改变。
    花了两个半月刷 leetcode,基本都解决了,其中大概有 10+ 道题目是参照答案来实现的。
    因为边工作所以整个过程不容易,常常陷入一道题目不能自拔,有时候熬夜来做题目。
    体会:
    1 数据结构和算法是计算机技术的基础,有时候可以体会到美感。每一个 coder 都应该加强这方面的知识。
    2 不要在乎题目本身,而是每个题目代表一定的背景知识,比如 dfs,剪枝,贪心和动态规划。
    3 竞技和工程化写代码毕竟还是不一样的,思维方式不一样,最开始做题很困难是正常的。
    4 实在想不出来可以看看提示,因为如果缺乏理论知识,怎么想也是想不出来的。

    注意点:
    1 建议从 AC Rates 排序的容易开始做起,能有一个良好的开始。
    2 oj 这方面还是以 cpp 为主,我使用 python 实现的,有一些算法基本一样,cpp 能过而 python 不能过。

    next:
    我准备回归理论知识,因为在这个过程发现理论知识不够,特别是数学类的分析。
    27 条回复    2017-03-12 14:15:37 +08:00
    likaci
        1
    likaci  
       2014-10-08 14:12:42 +08:00   ❤️ 1
    然后发现数学才是真爱,转行做数学去了……
    cloudzhou
        2
    cloudzhou  
    OP
       2014-10-08 14:20:42 +08:00
    @likaci 我还真的是很喜欢数学啊 :-),就是遗憾没有太多时间啊
    chengdujin
        3
    chengdujin  
       2014-10-08 14:49:36 +08:00
    同刷中,国庆刚过完一遍 也是用 Python :D

    还剩三道题感觉太麻烦,没做
    20.0% Regular Expression Matching
    14.0% Text Justification
    14.0% Wildcard Matching

    准备本周开始下一遍
    cloudzhou
        4
    cloudzhou  
    OP
       2014-10-08 15:02:41 +08:00   ❤️ 1
    @chengdujin Text Justification 难度很小,就是细节题目而已。
    Wildcard Matching 这道题目我也是放弃了,虽然使用递归实现了,但是 timeout 了。

    有一道题目我需要咨询一下:
    Longest Palindromic Substring
    这道题目使用 动态规划 是很明显的,复杂度 O(n^2),但是哪怕我照抄前人 cpp 的代码也不能通过。
    我知道有一种 O(n) 的解法,http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

    不知道是不是 leetcode 对这道题目的评判标准提高了?
    chengdujin
        5
    chengdujin  
       2014-10-08 15:27:05 +08:00   ❤️ 1
    @cloudzhou 哈 longest palindromic substring 我也是n^2的,没过折腾了两天,最后还是选择用自己的办法(所以最后还是问号不是勾)

    这道题我看讨论,n^2是过不了的,要用一个叫Manacher Algorithm的O(n)算法
    cloudzhou
        6
    cloudzhou  
    OP
       2014-10-08 15:37:29 +08:00
    @chengdujin 恩,看来是必须 O(n) 才能过,这个算法我就没有深究了。
    leetcode 有一些题目,包括一些面试题,有点“讨巧”的意味,我不认为这是好的面试题。
    对于个人,我更喜欢一些贴近现实的题目,比如 LRU 的实现,再引入并发,探讨空间很大,这是面试的好题目。
    yangff
        7
    yangff  
       2014-10-08 15:57:00 +08:00 via Android
    @cloudzhou mc是一个挺有用的算法。
    特别是它蕴含了一个字符串的本质不同的回文串是O(n)级别的
    cloudzhou
        8
    cloudzhou  
    OP
       2014-10-08 16:01:09 +08:00
    @yangff 还有人说可以使用后缀数组实现,也没有仔细看。等我补充一点理论知识再来做题 :-)
    lxgone
        9
    lxgone  
       2014-10-08 16:04:32 +08:00
    哎,最近找工作也刷leetcode,也是按照AC Rate从高到底来的,可惜还是木有刷完
    lushl9301
        10
    lushl9301  
       2014-10-08 16:45:33 +08:00
    回归理论真的必要么。
    我在几年前做竞赛,理论基础比较差,但是大量时间练习。大脑零落,编程快速准确。
    如今大学学习紧张,很少时间练习。虽然理论知识强了,但是编程水平下降到无法看。自己也一直觉得脑残。。非常不爽快。。。

    估计是可能需要通过刷题库来解决了。。
    cloudzhou
        11
    cloudzhou  
    OP
       2014-10-08 16:52:06 +08:00
    @lushl9301 所以这就是竞技和实际开发的不同啊。
    如果只是竞技,那就是不断的刷题,并且练习快速编程。
    如果为了加强计算机基础,提高实际掌握问题的能力,那就回归到理论。
    对我来说,竞技根本就没有必要,并且不是为了刷提为目的的,所以认真看书,加强理论知识才是我要做的。
    liuchang0812
        12
    liuchang0812  
       2014-10-08 22:41:11 +08:00 via Android
    @cloudzhou 可以过啊。。。。
    liuchang0812
        13
    liuchang0812  
       2014-10-08 22:41:49 +08:00 via Android
    dingyaguang117
        14
    dingyaguang117  
       2014-10-08 23:09:51 +08:00 via iPhone
    正则那题要是在大三学编译原理的时候肯定能做出来,nfa转dfa,不过现在完全不记得
    cloudzhou
        15
    cloudzhou  
    OP
       2014-10-08 23:59:38 +08:00
    @liuchang0812
    @chengdujin
    真是很神奇,@liuchang0812 的算法真的能过,我是参照 https://github.com/soulmachine/leetcode 里面的解法的,完全照抄也没有通过,这两者之间有什么不一样呢?
    cloudzhou
        16
    cloudzhou  
    OP
       2014-10-09 00:02:47 +08:00
    cloudzhou
        17
    cloudzhou  
    OP
       2014-10-09 00:18:07 +08:00
    @liuchang0812
    @chengdujin

    哈哈,我已经找到问题的关键了,这两者复杂度是一样的,soulmachine/leetcode 的方法更加好理解,如果注销了 fill_n(&f[0][0], n * n, false); 这一句就完全可以通过了。
    如果 @liuchang0812 加了 fill_n(&f[0][0], 1001 * 1001, 0); 这一句同样也是 Time Limit Exceeded 的,这真是个有趣的问题。

    从工程化来说:申请并且对内存段进行 zero 是一个很好的习惯。
    chenggiant
        18
    chenggiant  
       2014-10-09 00:53:25 +08:00 via iPhone
    膜拜一下!我刷了4个月了,还是只做了60题...
    liuchang0812
        19
    liuchang0812  
       2014-10-09 00:58:38 +08:00
    @cloudzhou
    这个数组,代码本来紧跟着就是初始化的过程.工程上来说也不应该多次对大内存操作,而且还是无用的操作.
    thinkmore
        20
    thinkmore  
       2014-10-09 09:01:58 +08:00
    数学很重要,可是天赋。。。
    cloudzhou
        21
    cloudzhou  
    OP
       2014-10-09 09:33:34 +08:00
    @liuchang0812 我对 c/c++ 不了解,之前看书的时候是推荐申请内存之后 memset zero,是一种编程上的防御手段吧。所以我也不了解现在默认情况下申请内存后就是 zero 的。

    谁对这一块了解的麻烦讲讲?
    wudikua
        22
    wudikua  
       2014-10-09 11:28:23 +08:00
    java实现的飘过~
    tension2012
        23
    tension2012  
       2014-10-09 14:47:41 +08:00
    test data貌似也不能看啊
    lushl9301
        24
    lushl9301  
       2014-10-09 21:20:04 +08:00
    @cloudzhou 我觉得如果这样想,看efficient cpp呀,code complete啊,programming pearls。再加上TAOCP,慢慢啃。哈哈。
    我是大一去啃APUE,看了有1/8. 看TAOCP一卷多,然后转到programming pearls。加油加油。。。希望找到一起学习计算机经典的人。。
    cloudzhou
        25
    cloudzhou  
    OP
       2014-10-10 09:31:59 +08:00
    @lushl9301 你们现在这种意识真好,以前迷迷糊糊不知道怎么学起,计算机就应该从基本理论,算法和数据结构开始学起
    John1984
        26
    John1984  
       2015-04-14 20:52:14 +08:00
    armstrong
        27
    armstrong  
       2017-03-12 14:15:37 +08:00
    真是羡慕你们呀,我是从今年才开始意识到这个问题,正在努力弥补中
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3211 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 11:37 · PVG 19:37 · LAX 04:37 · JFK 07:37
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.