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

有刷 leetcode 的伙伴吗?怎么看那些遇到链表题就先储存在数组里,然后处理最后输出在链表里的解法?

  •  
  •   russian · 2019-06-18 16:28:51 +08:00 · 1098 次点击
    这是一个创建于 1155 天前的主题,其中的信息可能已经有所发展或是发生改变。

    RT 刷 leetcode 发现不少这种链表题,然后有几次了,看到有人都是先把链表遍历一遍,储存在数组里,然后数组处理交换或者赋值,最后把结果输出在一个新的返回的链表里。。。

    总感觉这么干难道不是作弊?当然相当于是用空间换时间的一种解法。。。

    10 条回复    2019-06-18 19:10:29 +08:00
    lsvih
        1
    lsvih  
       2019-06-18 16:32:50 +08:00
    打比赛内存卡的比较死就过不了了。平常解题别人要取巧也没办法呗
    lucifer9
        2
    lucifer9  
       2019-06-18 17:11:49 +08:00
    我小时候写作业有练习循环的要输出个矩形之类,有些实在复杂懒得想了,我都是直接写 printf
    wqzjk393
        3
    wqzjk393  
       2019-06-18 17:18:27 +08:00
    因为链表很多时候需要用到指针和递归调用之类的,写法比较麻烦。其实说起来,反正又不是自己的事情,他爱偷鸡就偷吧
    russian
        4
    russian  
    OP
       2019-06-18 17:54:21 +08:00
    @lsvih 我发现这种解法在 leetcode 上竟然速度一半 80%往上,内存一半也是类似。。。什么鬼。我以后面试题也可以这么做卧槽
    当然 acm 应该是不行。
    WhoMercy
        5
    WhoMercy  
       2019-06-18 17:54:29 +08:00
    关于空间换时间:
    因为 LC 会卡运行时间,有超时的限制,但没遇到过超内存的情况。
    我的理解是,相当于变相允许空间换时间。


    关于偷懒的解法:
    我看的解法不多,一般只看排名靠前的那几个,有的解法比较有新意,比如代码量很少的、速度很快的、使用空间很小的,他们为了达到这个目的做了一些额外工作也可以理解吧,毕竟千篇一律的解法也没意思。


    如果真的需要做空间限制的,
    会有提示,类似于" Could you implement it without using extra memory",这样大家都会尽量考虑少使用空间吧。
    russian
        6
    russian  
    OP
       2019-06-18 17:55:43 +08:00
    @wqzjk393 关键是我发现面试题也可以这么偷鸡啊,特别是 online assessment。不太清楚如果当面这么写会不会被面试官喷。
    russian
        7
    russian  
    OP
       2019-06-18 17:57:37 +08:00
    @WhoMercy 关键是这么偷鸡也太爽了,几乎所有的链表题都可以这么简化,速度和内存使用还都是 80%的那种。卧槽
    x1nes
        8
    x1nes  
       2019-06-18 18:00:12 +08:00
    之前还看到过一个把所有测试用例的结果 用 if ,else if 挨个返回的,用了 3ms ,排名第一
    russian
        9
    russian  
    OP
       2019-06-18 18:28:38 +08:00
    @x1nes 这 tmd 的是真大佬了。。。
    mooncakejs
        10
    mooncakejs  
       2019-06-18 19:10:29 +08:00
    leetcode 的机制有问题,同样的提交,每次提交运行时间都不太一样,我猜是不同的测试在同一个机器上运行导致互相干扰结果不同,如果是数指令数就好了。
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4185 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 09:24 · PVG 17:24 · LAX 02:24 · JFK 05:24
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.