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

我感觉 LeetCode 上面对于代码的要求苛刻

  •  
  •   wdy1184 · 2015-02-13 15:01:14 +08:00 · 6179 次点击
    这是一个创建于 3331 天前的主题,其中的信息可能已经有所发展或是发生改变。
    新手,在leetcode上面做twosum.
    第一次用迭代器
    报错,超时
    第二次用数组下标
    报错,超时
    要求苛刻我觉得很好!我会继续努力的.
    32 条回复    2015-02-16 12:05:09 +08:00
    hcymk2
        1
    hcymk2  
       2015-02-13 15:05:05 +08:00
    我用java刷完50%的 题目 还没碰到time out 这是 LeetCode在歧视java么?
    ant_sz
        2
    ant_sz  
       2015-02-13 15:18:47 +08:00
    two sum 应该可以用 O(nlogn) 的时间复杂度搞定。如果不是 O(nlogn) 过不了太正常了
    exch4nge
        3
    exch4nge  
       2015-02-13 15:27:13 +08:00
    确定你是用O(nlogn)或更小的时间复杂度搞定的,但还是超时的话,看看你是不是把自己调试打印的语句没注释掉……
    binux
        4
    binux  
       2015-02-13 15:27:38 +08:00   ❤️ 3
    这。。LeetCode 上面的题都太简单了,完全是在考 bug free 而不是算法的。。
    gandblack
        5
    gandblack  
       2015-02-13 15:28:24 +08:00   ❤️ 1
    不苛刻吧,话说Median of Two Sorted Arrays 写明要log(m+n)的时间复杂度,,你怎么破
    或者two sum也写明要求 O(nlogn)的时间复杂度你就不会纠结下标还是迭代了
    ivanlw
        6
    ivanlw  
       2015-02-13 15:36:35 +08:00
    two sum 不是没有用O(n)做出来的面试直接刷掉吗?
    caizixian
        7
    caizixian  
       2015-02-13 15:52:34 +08:00
    rangercyh
        8
    rangercyh  
       2015-02-13 15:56:34 +08:00
    @binux 说的对,leetcode的题目确实不是考难度,而是考bug free,其实很适合算法新手做
    caizixian
        9
    caizixian  
       2015-02-13 15:57:16 +08:00
    @wdy1184 其实我用的也是数组下标法,关键用了Python,就把dict当array用了下。

    @binux @ivanlw 求看有无更好地实现
    ivanlw
        10
    ivanlw  
       2015-02-13 16:07:01 +08:00   ❤️ 1
    @caizixian 利用不同编程语言的hash set类型(不同语言有不同的叫法,C++是#include <unordered_set>,Java和Python的麻烦自己找一下)的look up time是O(1)的特性,跑一次就行了,举个例子吧(2, 7, 11, 15)找22:

    定义一个hashset就暂时叫a吧,一开始a是空的;先跑到2,找一下a里面有没有22-2=20(时间O(1)), 没有,把2存进a;然后7,找一下a里面有没有22-7=15,没有,把7存进去;跑到11,找一下a里面有没有22-11=11,没有把11存进去;跑到15,找一下a里面有没有22-15=7,有,所以两个数字就是7和15
    caizixian
        11
    caizixian  
       2015-02-13 16:09:26 +08:00
    @ivanlw 我就是这么写的。不过这样算作弊吧
    gandblack
        12
    gandblack  
       2015-02-13 16:34:08 +08:00
    @ivanlw 不是O(n)直接刷掉?有没有这么狠。。。。求一个时间空间复杂度都O(n)的解法
    wilsoncao
        13
    wilsoncao  
       2015-02-13 17:23:12 +08:00
    @binux @rangercyh 我觉得bug free就很难了。。。
    DaniloSam
        14
    DaniloSam  
       2015-02-13 17:39:21 +08:00   ❤️ 1
    ```python
    class Solution:
    # @return a tuple, (index1, index2)
    def twoSum(self, num, target):
    result = {}
    for i, n in enumerate(num, 1):
    if target - n not in result:
    result[n] = i
    else:
    return result[target - n], i

    return ()
    ```

    用hash table,O(n)啊不会超时啊
    JackWindows
        15
    JackWindows  
       2015-02-13 19:28:20 +08:00
    @binux 说出了我的心声。各位大神如果真想锻炼的话去做noi.openjudge.cn吧
    GtDzx
        16
    GtDzx  
       2015-02-13 19:44:58 +08:00
    @JackWindows 赞!没想到还有人知道noi.openjudge.cn这个题库。这个题库完成的话应该是很好的练习去处。
    twistoy
        17
    twistoy  
       2015-02-13 19:47:33 +08:00
    @JackWindows OIer?
    udonmai
        18
    udonmai  
       2015-02-13 21:59:30 +08:00   ❤️ 1
    每个人随便交个最 naive 的方法就过了,leetcode 也就没存在的必要了。。所以它多卡一点时间太正常了。。再者,你随便写了个方法想都不想就过了,你能学到什么。。
    wdy1184
        19
    wdy1184  
    OP
       2015-02-13 22:19:03 +08:00
    @DaniloSam 我用的是C++,不要剧透哦,我想自己来~
    wdy1184
        20
    wdy1184  
    OP
       2015-02-13 22:19:34 +08:00
    @hcymk2 没用java,可能java有更好的方法吧
    phoeagon
        21
    phoeagon  
       2015-02-13 22:26:11 +08:00
    @ivanlw 要排序啊。
    phoeagon
        22
    phoeagon  
       2015-02-13 22:26:27 +08:00
    @JackWindows 去spoj!
    ember
        23
    ember  
       2015-02-13 23:03:02 +08:00
    @GtDzx 卧槽惊现轩哥
    ivanlw
        24
    ivanlw  
       2015-02-14 07:50:19 +08:00 via iPhone
    @phoeagon 排序就至少O(nlogn),比这样子慢
    phoeagon
        25
    phoeagon  
       2015-02-14 09:06:03 +08:00
    @ivanlw 你可以用hash table我就基数排序!
    bugcoder
        26
    bugcoder  
       2015-02-14 21:53:27 +08:00
    @ivanlw
    @caizixian
    @phoeagon
    hashset 不行,输入里面有重复的元素
    bugcoder
        27
    bugcoder  
       2015-02-14 21:57:11 +08:00
    @DaniloSam
    测试数据里面有: [0,4,3,0], 0
    要求答案是唯一的
    bugcoder
        28
    bugcoder  
       2015-02-14 22:07:39 +08:00
    class Solution:

    # @return a tuple, (index1, index2)
    def twoSum(self, num, target):
    sumlen = len(num)
    for reverseindex in range(sumlen):
    sub = target - num.pop()
    if sub in num:
    return (num.index(sub)+1, sumlen-reverseindex)

    通过了,不过感觉不是最好的
    bugcoder
        29
    bugcoder  
       2015-02-14 22:13:07 +08:00
    @DaniloSam
    为什么python code的格式都没有了呢,难道只能楼主才能保持格式?
    DaniloSam
        30
    DaniloSam  
       2015-02-15 08:54:12 +08:00 via iPhone
    @bugcoder 要贴gist看来

    我这么写答案是唯一啊,返回应该是1,4,这个case怎么了
    wdy1184
        31
    wdy1184  
    OP
       2015-02-16 12:02:49 +08:00
    果然要用hash表,不太会算时间复杂度,只是知道了这个是O(n)的复杂度.
    wdy1184
        32
    wdy1184  
    OP
       2015-02-16 12:05:09 +08:00
    @ant_sz 我用了,先排序,再找,可是要返回的是数组的下标,所以这个不管用
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2711 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 34ms · UTC 15:38 · PVG 23:38 · LAX 08:38 · JFK 11:38
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.