V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
20015jjw
V2EX  ›  问与答

这道题在 O(1)空间下可能完成么?

  •  
  •   20015jjw · 2015-07-13 01:02:53 +08:00 · 2825 次点击
    这是一个创建于 3407 天前的主题,其中的信息可能已经有所发展或是发生改变。

    https://leetcode.com/problems/palindrome-linked-list/

    我怎么觉得不能... 各位学过算法的球指点...

    24 条回复    2015-07-13 16:39:01 +08:00
    IwfWcf
        1
    IwfWcf  
       2015-07-13 01:28:50 +08:00
    可以做到,只是比较麻烦……

    第一次遍历得到长度,确定中点;第二次遍历将中点之前的 list reverse,然后进行比较;第三次遍历将中点之前的 list 再次 reverse,恢复原始 list
    qw7692336
        2
    qw7692336  
       2015-07-13 01:48:17 +08:00
    创建多一条出来。
    qw7692336
        3
    qw7692336  
       2015-07-13 01:48:46 +08:00
    @qw7692336 不对不对,不允许这么做
    Andiry
        4
    Andiry  
       2015-07-13 02:03:12 +08:00   ❤️ 2
    严格意义上不可能。任何需要修改原始输入的解法(比如原地reverse list)都不能算是O(1)空间复杂度。
    20015jjw
        5
    20015jjw  
    OP
       2015-07-13 02:16:50 +08:00
    @IwfWcf reverse就需要存储关于n变大二变大的数据啊... 不管是弄个pointer往前指 还是把数据存在外部结构里...
    sumhat
        6
    sumhat  
       2015-07-13 03:01:46 +08:00
    如果递归不算额外空间的话,也是可以的。
    20015jjw
        7
    20015jjw  
    OP
       2015-07-13 03:59:59 +08:00 via Android
    @sumhat 如果利用额外空间不算的话,递归也是O(1)………
    zhyu
        8
    zhyu  
       2015-07-13 07:08:58 +08:00 via iPhone
    @IwfWcf reverse和查找中点可以同时完成
    @20015jjw reverse哪有那么多中间变量,就需要一个临时节点
    wy315700
        9
    wy315700  
       2015-07-13 07:46:51 +08:00
    很简单啊

    在操场上,两个人跑步,如果两个人速度不一样,那么,最终快的那个人会整整比慢的那个人快一圈的。
    俗称套圈。

    所以,弄两个指针,一个一次前进一步,一个一次前进两步,如果他们最终相遇了,那么就是存在环,否则就没有。

    2011年银联面试题考过。
    wy315700
        10
    wy315700  
       2015-07-13 07:48:19 +08:00
    不对,看错题了,无视我吧
    20015jjw
        11
    20015jjw  
    OP
       2015-07-13 09:36:02 +08:00
    @zhyu 一个linkedlist如果有10000个link,需要10000个额外的pointers,然而如果只有1个,那就只需要一个额外的pointers,这不就是O(n) space么....
    alafeizai
        12
    alafeizai  
       2015-07-13 09:54:16 +08:00
    @20015jjw 并没有多申请空间,而是利用了原有的next指针,只利用了一个中间变量做缓存。
    xcv58
        13
    xcv58  
       2015-07-13 09:56:49 +08:00
    1L 正解

    这题相当无聊。
    20015jjw
        14
    20015jjw  
    OP
       2015-07-13 10:08:38 +08:00 via Android
    @alafeizai 不懂... 我说的情况里长度为1和长度为10000的list需要的缓存一样多么?如果一样多,请问怎么实现呢?
    yangff
        15
    yangff  
       2015-07-13 10:20:05 +08:00 via Android
    不要慌。。上hash
    20015jjw
        16
    20015jjw  
    OP
       2015-07-13 10:31:34 +08:00 via Android
    @20015jjw

    好吧现在懂了 reverse list的时候只是用了原来的pointer 唯一需要增加的只是指向中点的pointer...

    但是还是有点虚... 因为上午问大神大神说算法课学过palindrome问题不能是O(1) space
    IwfWcf
        17
    IwfWcf  
       2015-07-13 10:33:55 +08:00
    @zhyu 为什么可以同时完成?不先进行一次遍历怎么能知道 reverse 的时候在哪个节点停下来?

    @20015jjw

    node = head;
    next = node->next;
    while (next) {
    tmp = next->next;
    next->next = node;
    node = next;
    next = tmp;
    }
    IwfWcf
        18
    IwfWcf  
       2015-07-13 10:38:55 +08:00
    @zhyu 哦,知道了,用两个指针来移动
    zhyu
        19
    zhyu  
       2015-07-13 11:27:13 +08:00
    @IwfWcf https://gist.github.com/zhyu/662d0a0aa88c5e21c31e
    没写恢复指针的部分
    恢复和判断也可以同时完成
    IwfWcf
        20
    IwfWcf  
       2015-07-13 13:27:33 +08:00
    @zhyu 嗯,是的,这样就可以 AC 了?我之前用 C++ 交别的题的时候如果改变了传入的引用内容是会判错的
    zhyu
        21
    zhyu  
       2015-07-13 14:23:55 +08:00
    @IwfWcf 题目链接?我不记得遇到过不能改传入值的题。。
    IwfWcf
        22
    IwfWcf  
       2015-07-13 15:29:37 +08:00
    @zhyu 找不出来了,当时也没有特别记录,和这题类似最后 return bool,但我改了传入的 vector 的内容就被判错
    ffffwh
        23
    ffffwh  
       2015-07-13 16:27:40 +08:00
    弱问链表的回文是个啥...
    rcmerci
        24
    rcmerci  
       2015-07-13 16:39:01 +08:00
    吓尿了。。看成O(1)time了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2748 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 01:58 · PVG 09:58 · LAX 17:58 · JFK 20:58
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.