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

在做 LeetCode OJ,有题做不出,答案也看不懂,觉得自己很蠢怎么办

  •  
  •   kevinyoung · 2014-10-25 16:52:51 +08:00 · 15378 次点击
    这是一个创建于 3667 天前的主题,其中的信息可能已经有所发展或是发生改变。
    挑到maximum subarray这题了: https://oj.leetcode.com/problems/maximum-subarray/

    想了半天写不出,去google发现有wiki的页面,但是上面给的答案简洁则已,自己居然连为什么是对的都看不出,上面还说这个解法是简单的动态规划,根本不明白啊,觉得自己太蠢了,是不是该收拾收拾回家种田好了
    第 1 条附言  ·  2014-10-25 19:44:29 +08:00
    感谢各位的回复,吐槽完就看明白答案了,然后顺便把分冶的给写了,但是我的python版超内存限制了,就没再看了。

    算法导论我也看了,动态规划还没讲明白先被例子给搅迷糊了,这书感觉适合当reference,学习算法的话推荐Udi Manber的算法引论: http://book.douban.com/subject/1436134/

    同样是讲动态规划,一页纸就说完了,例子也清楚的多,关键是书本详细介绍了如何用数学归纳没法设计分析算法,真熟练了的话可以砍瓜切菜,我这才刚开始,所以做题还是被虐....

    @mitcc 推荐了数据结构与算法分析——c语言描述,听说不错,但还没来得及看 http://book.douban.com/subject/1139426/

    @icylogic 推荐了普林斯顿在coursera上开的算法课,第一部分已经完结,第二部分还有5天开课,但是也太龟毛了,上完就不给看存档了。我自己抓了一份放在度盘上,刚想分享一下的,但是试了四次都是直接被抽,蛋都碎了...
    第 2 条附言  ·  2014-10-25 19:48:59 +08:00
    我又去看了,普林斯顿的算法课还能看存档,用这个链接: https://class.coursera.org/algs4partI-006

    需要的赶紧保存一下
    15 条回复    2016-06-23 01:23:15 +08:00
    jsonline
        1
    jsonline  
       2014-10-25 17:07:39 +08:00 via Android   ❤️ 1
    先看算法导论吧
    sethverlo
        2
    sethverlo  
       2014-10-25 17:35:42 +08:00 via iPhone   ❤️ 1
    不建议算法导论,想省事儿就搜下动态规划相关的博客。
    hustlike
        3
    hustlike  
       2014-10-25 17:51:00 +08:00   ❤️ 1
    看不懂不一定是因为蠢,因为很多人都不会。网上教的学算法的方法我觉得基本上都是不切实际的,比如沙发。首先期望要放低一点。。
    txx
        4
    txx  
       2014-10-25 17:54:41 +08:00   ❤️ 1
    沒經過大腦寫了一個 簡單粗暴地 轉移方程...

    f(i) 表示 0~i 且選擇第i位的最優值

    f(i) = max(A[i], f(i-1) + A[i])
    f(0) = A[0]

    f 數組中最大的數 即為所求....
    binux
        5
    binux  
       2014-10-25 18:01:25 +08:00   ❤️ 1
    这题也挺逗的,你想到 O(N) 之后你用分治,我以为分治有多巧妙呢,想半天都是 O(NlogN),结果看讨论,分治就是 O(NlogN) 的。。
    mitcc
        6
    mitcc  
       2014-10-25 18:23:19 +08:00   ❤️ 1
    对于这一题,我推荐你看一下Mark Allen Weiss写的那本《数据结构与算法分析——C语言描述》的第2章中的最大子序列求和问题,从O(n^3)到O(n^2)到O(nlgn),最后到O(n),循序渐进,当时我看到这儿时,被这种讲法给震到了,如此简洁明了,毫无理解障碍,尤其是从O(n^3)到O(n^2),他会告诉你怎么省掉一些开销。

    反观国内某人写的某本高校广泛使用的数据结构,看得头疼,代码完全不能运行,不说也罢,偏题了,不好意思。
    xcv58
        7
    xcv58  
       2014-10-25 18:39:27 +08:00 via iPad   ❤️ 1
    先写简单的程序把测试用例弄出来些。然后一个例子一个例子地看,手工怎么算。然后尝试扩展成程序,再考虑如何优化。
    jox
        8
    jox  
       2014-10-25 18:41:04 +08:00   ❤️ 1
    lz不要灰心啊,这种算法题有点像脑筋急转弯,也有点像锻炼身体,多练练就好了
    icylogic
        9
    icylogic  
       2014-10-25 18:51:13 +08:00   ❤️ 1
    同在刷 leetcode, 这道题以前在 @mitcc 提到的那本书里见过.

    不过这本书讲得有点简单, 类似 K&R 这个级别的, 现在就着公开课在慢慢看 clrs , 虽然一开始有点晕, 看到第三章开始有点习惯了......

    有很多人推荐 Coursera 的那个普林斯顿开的 Algorithm, 对应的书是 <算法 第四版> 有中文版.
    qiukun
        10
    qiukun  
       2014-10-25 19:21:14 +08:00
    @mitcc 我校某本教材就是这么讲的
    kevinyoung
        11
    kevinyoung  
    OP
       2014-10-25 19:45:09 +08:00
    @txx 你可以去试试,不对...
    txx
        12
    txx  
       2014-10-25 20:09:30 +08:00
    @kevinyoung 我表示提交 AC 了啊~
    qiukun
        13
    qiukun  
       2014-10-25 20:11:22 +08:00
    @binux 分治在并行条件下有优势呀
    wizardforcel
        14
    wizardforcel  
       2014-12-03 16:28:05 +08:00 via Android
    这题是联机算法,我也没搞懂。

    sum = max(sum + a[i], a[i]);
    maxsum = max(sum, maxsum);
    vjnjc
        15
    vjnjc  
       2016-06-23 01:23:15 +08:00
    @txx 嘿哥们我在面试的时候遇到这个题了。结果当然是我没做出来 0 0
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2703 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 12:30 · PVG 20:30 · LAX 04:30 · JFK 07:30
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.