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

20180323 今日算法

  •  
  •   gbin · 146 天前用 Android 发布 · 2089 次点击
    这是一个创建于 146 天前的主题,其中的信息可能已经有所发展或是发生改变。
    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
        1
    lhx2008   146 天前 via Android
    split 之后,递归到尾部,返回的时候拼接
        2
    gbin   146 天前 via Android
    @lhx2008 思路不错。
        3
    cloverii   146 天前 via Android
    我某次三面的时候被问过这题,所以这是个考栈的题么…我直接像 1L 那样说了 因为面试官说让我用 Python 写…
        4
    lhx2008   146 天前 via Android   ♥ 1
    split 之后,头尾之间交换也可以,扫 1.5 次,空间复杂度更优
        5
    gbin   146 天前 via Android
    @cloverii 我倒觉得用递归比用栈好吧,二者空间复杂度都是 O(n),递归时间复杂度 O(n),栈 O(2n)。我看到给的提示说有更厉害的方法只需 O(1),只是没去查过,看看有没有大神提出来吧。
        6
    66450146   146 天前 via iPhone   ♥ 6
    整个字符串反转,再扫一遍每个词反转即可,空间 O1
        7
    zc666   146 天前 via iPad
    python 的话可以直接 split 之后数组下标从-1 开始然后下标每次递减 1,当出现 list index out of range 错误之后即是倒序遍历完了
        8
    iEverX   146 天前 via Android
    通常还会加上原地的限制,用 split,面试官一般不会满意的。当然 python 就没办法了
        9
    gbin   146 天前 via Android
    @iEverX 所以我认为#6 楼最有道理。
        10
    thebigban   146 天前 via Android
    @gbin 六楼这个有问题,如果反转,单词也被反转了。
        11
    hx1997   146 天前 via Android
    分割之后倒着拼接,或者栈,只会这俩
        12
    gbin   146 天前 via Android
    @thebigban 没有吧,先整个字符串反转再单词反转呢。
        13
    zoffy   146 天前   ♥ 1
    js:

    "the sky is blue".split(' ').reverse().join(' ')
        14
    thebigban   146 天前 via Android
    @gbin 看错了。。。
        15
    tongz   146 天前
    php:
    $str = "the sky is blue";

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

    println!("{:?}", rev_s);
    }
        20
    gbin   146 天前 via Android
    @zqqian 出难一点的讨论的不多呀,你看昨天前天
        21
    gbin   146 天前 via Android
    @gbin 可能你比较厉害😂😂觉得简单
        22
    snw   146 天前 via Android
    可以把题目改成字符串大于内存,但每个词小于内存😂
        23
    xgzxy   146 天前
    @snw 你这个想法不错
        24
    pagict   146 天前
    ```python
    ' '.join(line.split()[::-1])
    ```
        25
    yianing   146 天前
    #24 估计是最简单的了
        26
    WilliamLin   145 天前 via Android
    Python 的话就用 split 加 reverse 加 join
        27
    mrcn   145 天前 via Android
    @snw 有正解吗?感觉不能做到倒着输入 /输出。。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   鸣谢   ·   实用小工具   ·   3050 人在线   最高记录 3762   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.1 · 24ms · UTC 07:55 · PVG 15:55 · LAX 00:55 · JFK 03:55
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1