要注意的是特殊字符的位置(例如:'?'、','、''、'.')应该保持不变。所以对于输入字符串“Hello World,你好吗?”输出将是“you are, how World Hello?”。现在对于没有特殊字符的字符串,O(n) 算法是将每个单词反转,然后反转整个数组,但不考虑特殊字符。
我想出的最佳算法如下。我们遍历数组并将每个单词压入堆栈顶部,然后将特殊字符放入队列中。稍后,我们同时从堆栈和队列中弹出元素,并将它们连接起来以形成所需的输出。
是否有就地 O(n) 算法?如果没有,您能否建议一个没有额外空间的 O(n^2) 算法。还假设您不能使用任何字符串库函数。
最佳答案
所以,这是一个想法。
1) 初始字符串
"Hello World, how are you?"
2) 反转字符串,但不包含任何最后的特殊字符
"uoy era woh ,dlroW olleH?"
3) 反转字符串中的单词
"you are how ,World Hello?"
4) 创建一个指向字符串开头和结尾的迭代器(指针、索引,无论您使用什么),递增/递减每个迭代器,直到它们命中非单词。非文字是指空格或特殊字符。因此,在这种情况下,递增迭代器将首先遇到“you”和“are”之间的空格,而递减迭代器将遇到“world”和“Hello”之间的空格,如下所示。
"you are how ,World Hello?"
^ ^
5) 如果没有特殊字符,继续,如果你打了一个特殊字符。反转迭代器之间的所有内容,包括它们指向的字符。下面显示了这种情况发生的时间
"you are how ,World Hello?"
^ ^
6) 现在我们看到了反转的结果。
"you are, woh World Hello?"
根据 johnchen902 的评论进行编辑
7) 现在反转这些迭代器之间的子字符串,不包括在步骤 (5) 中找到的特殊字符。
"you are, how World Hello?"
8) 返回步骤(5)
我还没有编写代码,解释起来有点棘手,但我希望你能理解
关于c++ - 反转字符数组中单词的顺序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17594940/