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

发布于 2022-09-01 05:07:41 字数 405 浏览 17 评论 0

例如：i am sad 变成 sad am i

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

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

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

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

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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

无所谓啦 2022-09-08 05:07:42

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

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

回复收藏 0

小矜持 2022-09-08 05:07:42

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

回复收藏 0

抠脚大汉 2022-09-08 05:07:42

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

        print  word

回复收藏 0

孤寂小茶 2022-09-08 05:07:42

php<?php

$str = 'i  am  sad';

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

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

回复收藏 0

你是年少的欢喜 2022-09-08 05:07:42

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

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不一定需要使用结构体，直接搞个很长的数组也可以，不过就是太浪费内存了。

回复收藏 0

深居我梦 2022-09-08 05:07:42

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

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

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

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

回复收藏 0

浅唱ヾ落雨殇 2022-09-08 05:07:42

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

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();
        }
    }
}

回复收藏 0