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

20180323 今日算法

  •  
  •   gbin · 2018-03-23 08:13:10 +08:00 via Android · 4363 次点击
    这是一个创建于 2421 天前的主题,其中的信息可能已经有所发展或是发生改变。
    Given an input string, reverse the string word by word.

    For example,
    Given s = "the sky is blue",
    return "blue is sky the".

    PS: 今天题目不算难,一种方法是用栈,是 O(n)的复杂度,看看各位有什么巧妙的方法吧。
    27 条回复    2018-03-23 22:30:40 +08:00
    lhx2008
        1
    lhx2008  
       2018-03-23 08:15:37 +08:00 via Android
    split 之后,递归到尾部,返回的时候拼接
    gbin
        2
    gbin  
    OP
       2018-03-23 08:22:16 +08:00 via Android
    @lhx2008 思路不错。
    cloverii
        3
    cloverii  
       2018-03-23 08:28:12 +08:00 via Android
    我某次三面的时候被问过这题,所以这是个考栈的题么…我直接像 1L 那样说了 因为面试官说让我用 Python 写…
    lhx2008
        4
    lhx2008  
       2018-03-23 08:34:15 +08:00 via Android   ❤️ 1
    split 之后,头尾之间交换也可以,扫 1.5 次,空间复杂度更优
    gbin
        5
    gbin  
    OP
       2018-03-23 08:37:10 +08:00 via Android
    @cloverii 我倒觉得用递归比用栈好吧,二者空间复杂度都是 O(n),递归时间复杂度 O(n),栈 O(2n)。我看到给的提示说有更厉害的方法只需 O(1),只是没去查过,看看有没有大神提出来吧。
    66450146
        6
    66450146  
       2018-03-23 08:41:18 +08:00 via iPhone   ❤️ 6
    整个字符串反转,再扫一遍每个词反转即可,空间 O1
    zc666
        7
    zc666  
       2018-03-23 08:42:10 +08:00 via iPad
    python 的话可以直接 split 之后数组下标从-1 开始然后下标每次递减 1,当出现 list index out of range 错误之后即是倒序遍历完了
    iEverX
        8
    iEverX  
       2018-03-23 08:57:03 +08:00 via Android
    通常还会加上原地的限制,用 split,面试官一般不会满意的。当然 python 就没办法了
    gbin
        9
    gbin  
    OP
       2018-03-23 09:00:11 +08:00 via Android
    @iEverX 所以我认为#6 楼最有道理。
    thebigban
        10
    thebigban  
       2018-03-23 09:05:56 +08:00 via Android
    @gbin 六楼这个有问题,如果反转,单词也被反转了。
    hx1997
        11
    hx1997  
       2018-03-23 09:06:57 +08:00 via Android
    分割之后倒着拼接,或者栈,只会这俩
    gbin
        12
    gbin  
    OP
       2018-03-23 09:07:17 +08:00 via Android
    @thebigban 没有吧,先整个字符串反转再单词反转呢。
    zoffy
        13
    zoffy  
       2018-03-23 09:23:21 +08:00   ❤️ 1
    js:

    "the sky is blue".split(' ').reverse().join(' ')
    thebigban
        14
    thebigban  
       2018-03-23 09:37:21 +08:00 via Android
    @gbin 看错了。。。
    tongz
        15
    tongz  
       2018-03-23 09:51:37 +08:00
    php:
    $str = "the sky is blue";

    echo implode(' ', array_reverse(explode(' ', $str)));
    cloverii
        16
    cloverii  
       2018-03-23 10:35:36 +08:00 via Android
    @gbin 发现我把一楼看错了…并不知道怎么递归…重翻了一下面经,发现面试官这题问得很随意,于是我也很随意的说 split 一下再倒着输出,他没有进一步问了…(我一直觉得是因为我说用 py 写过点小爬虫,所以他问了我一个 sb 问题看我到底会不会写 py,现在突然觉得好像不是那么回事了…可能这就是我过了面试但是钱并不多的原因吧[手动狗头]
    zqqian
        17
    zqqian  
       2018-03-23 10:48:36 +08:00 via Android
    lz 可以出点不这么简单的题么。。。。。
    domty
        18
    domty  
       2018-03-23 11:01:58 +08:00
    变形的翻转字符串。
    muziki
        19
    muziki  
       2018-03-23 11:42:30 +08:00
    fn main() {
    let s = "the sky is blue";
    let rev_s = s.split_whitespace().rev().collect::<Vec<&str>>().join(" ");

    println!("{:?}", rev_s);
    }
    gbin
        20
    gbin  
    OP
       2018-03-23 12:13:33 +08:00 via Android
    @zqqian 出难一点的讨论的不多呀,你看昨天前天
    gbin
        21
    gbin  
    OP
       2018-03-23 12:14:18 +08:00 via Android
    @gbin 可能你比较厉害😂😂觉得简单
    snw
        22
    snw  
       2018-03-23 12:56:19 +08:00 via Android
    可以把题目改成字符串大于内存,但每个词小于内存😂
    xgzxy
        23
    xgzxy  
       2018-03-23 13:20:40 +08:00
    @snw 你这个想法不错
    pagict
        24
    pagict  
       2018-03-23 13:38:52 +08:00
    ```python
    ' '.join(line.split()[::-1])
    ```
    yianing
        25
    yianing  
       2018-03-23 15:25:26 +08:00
    #24 估计是最简单的了
    WilliamLin
        26
    WilliamLin  
       2018-03-23 18:19:18 +08:00 via Android
    Python 的话就用 split 加 reverse 加 join
    mrcn
        27
    mrcn  
       2018-03-23 22:30:40 +08:00 via Android
    @snw 有正解吗?感觉不能做到倒着输入 /输出。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3339 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 11:30 · PVG 19:30 · LAX 03:30 · JFK 06:30
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.