面试题：句子中的单词顺序翻转，每个单词的字母顺序不变

Question

例如：i am sad 变成 sad am i

这个题目在我面试的时候，一位面试官问过我。当时让我在纸上写代码，写半天我没写出来，我还是比较弱的。

不过一直让我纠结的是，面试官说我这方法一般：

• 我给出的思路是：扫描一遍所有的字母，边扫描边切分单词压栈，最后再从栈里弹出。
• 而面试官说这是很常见的一道面试题：两次翻转(首先将句子全部翻转，再扫描一次将每个单词翻转)

这个问题时不时就会在我脑子里出现。我总觉得我的这个做法应该不错啊。我的想法是这个应用在实际场景中时，用来处理文章，当文档单词在一定数量级以上的时候，两次翻转的时间上应该会比我压栈这样差很多吧。

想着可能是自己脑子不太灵光，有什么点没想到的，来sf问问各位大大~~望不吝赐教

Answer 1

我觉得你的方法挺好的了, 就是多费了内存. 多考虑一点的话, 比如单词之间不一定是一个空格, 也许是多个, 这样你的方法就不适用了.

这确实是一个很老的面试题了.

Answer 2

'i am sad'.split(' ').reverse().join(' ');
是我想太简单了吗？

Answer 3

pythonfor word in reversed(words.split(" ")):
    if word.strip():

        print  word

Answer 4

php<?php

$str = 'i  am  sad';

// 以空格拆分字符串为数组，并将数组倒置
$words = array_reverse(explode(' ', $str));

// 拼接字符串，同时去掉多余的空格
$newStr = '';
foreach ($words as $word) {
    if ('' !== $word) {
        $newStr .= ' ' . $word;
    }
}
// 输出结果
echo trim($newStr);

Answer 5

今天下午有事，所以先给个思路，
这段文字可以看作是个二维数组，

char str[0] ="sad";
char str[1] = " ";//注意有空格的
char str[2] = "am";
...... 
char str[4] = "i";

既然是二维数组只需要把第一维的数据倒序，第二维的不变即可，即使，先输出str[4],然后str[3].....。即可。
但是由于c的数组是线性表，所以不太好办，
我们只能用双向链表来模拟。2个链表。

typedef struct str {
    WORD * word;
    STR * pre;
    STR * next;
}STR;
typedef struct word {
    int letter;
    WORD * next;
}WORD;

那么，接下来遍历句子，导入str结构体中，因为是双向循环链表，反向输出即可。
对于中间间隔不一定是空格问题，其实也好办，
把两个单词之间的内容（不管是空格还是逗号，符号，）也看作是一个单词，一个空格可以看着是只有一个空格的单词，如果是既有逗号也有空格，可以看作是一个单词，里面包含的是空格和逗号。
一般而言，单词的长度都不太长，所以，word不一定需要使用结构体，直接搞个很长的数组也可以，不过就是太浪费内存了。

Answer 6

数据量小的时候确实没啥差距，放大规模考虑问题的思路是对的

放大规模以后，楼主的算法的问题在于空间成本，两次扫描的算法需要的额外内存不会随数据量的增加而增加，是O(1)的，而楼主的堆栈明显需要一倍以上O(N)的内存，数据量到G到T以后内存就崩溃了，但基于扫描的算法仍能很好的工作

这也就是为什么流的概念在越来越多的语言／类库中被放上重要的位置

不过两次扫描两次交换确实难以说是最好吧，我觉得可以考虑分块倒过来扫描啊，比如1G的文件先读最后的4K，输出，再读4K，输出，做好衔接就行

Answer 7

直接从串末往串首读，用栈做辅助来翻转单词。

cppvoid reverse(char* words)
{
    int i = strlen(words) - 1;
    while(i >= 0)
    {
        while(i >= 0 && words[i] == ' ')
        {
            printf(" ");
            i--;
        }
        stack<char> word;
        while(i >= 0 && words[i] != ' ')
            word.push(words[i--]);
        while(!word.empty())
        {
            printf("%c",word.top());
            word.pop();
        }
    }
}

Answer 8

这个要用递归循环算法效率最高，相当于一般的loop的2分之一的速度

Answer 9

第一个和最后一个交换，第二个和倒数第二个交换，一直到i<j不成立
i代表第一个元素，j代表最后一个元素

Answer 10

unwords . reverse . words $ "i am  sad"

Answer 11

原位完全颠倒的话，实际是第一个和最后一个对换，第二个和倒数第二个对换……所以也是线性复杂度。所以从时间复杂度上说两个算法相仿（事实上我觉得两次颠倒可能还会比压栈弹栈更快一些），但是空间复杂度上的优势是不言而喻的……

Answer 12

如果是一个比较大的文件，Java使用RandomAccessFile倒着单字符读取，遇到空格flush一次单词（读取进单词是反的，要reverse一次）。既解决速度也解决内存