4

问题是特殊字符的位置（例如：'?'、','、''、'.'）应该保持不变。所以对于输入字符串“Hello World，你好吗？” 输出将是“你是，你好吗？世界你好？”。现在对于没有特殊字符的字符串，O(n) 算法是反转每个单词，然后反转整个数组，但这并没有考虑特殊字符。

我想出的最佳算法如下。我们遍历数组并将每个单词压入堆栈顶部，然后将特殊字符排入队列。然后，我们同时从堆栈和队列中弹出元素，并将它们结合起来形成所需的输出。

是否有就地 O(n) 算法？如果没有，您能否建议一个没有额外空间的 O(n^2) 算法。还假设您不能使用任何字符串库函数。

4

2 回答 2

5

所以，这是一个想法。

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)。

我还没有编码，解释起来有点棘手，但我希望你能理解

于 2013-07-11T14:13:58.630 回答
1

对于就地算法，只需创建两个迭代器（对单词进行迭代），一个反向迭代器，另一个向前迭代。

您的循环将仅包含以下内容：

while(FirstIteratorIsBefore(forward_iterator, backward_iterator)) {
  if(IsSpecialCharacter(*forward_iterator)) {
    ++forward_iterator;
  } else if(IsSpecialCharacter(*backward_iterator)) {
    ++backward_iterator;
  } else {
    // Swap the two
    Swap(forward_iterator, backward_iterator);
    ++forward_iterator;
    ++backward_iterator;
  }
}

注意：您必须创建自己的简单单词迭代器才能使此逻辑正常工作，但这很容易实现。

于 2013-07-11T13:48:12.990 回答