LeetCode151. 反转字符串中的单词

丰收在望

拿到这道题，我们想一下，我们将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了。
所以解题思路如下：
移除多余空格
将整个字符串反转
将每个单词反转
举个例子，源字符串为："the sky is blue "
移除多余空格 : "the sky is blue"
字符串反转："eulb si yks eht"
单词反转："blue is sky the"
这样我们就完成了翻转字符串里的单词。
那么现在的思路就非常清晰明了了，先将整个字符串进行反转，再去除多余的空格，最后将每个单词进行反转
以下我对最难的部分---移除多余的空格进行讲解：
我们可以采用双指针的思想进行移除多余空格的操作，快指针用来遍历我们的数组，慢指针用于更新我们需要保留的元素的索引
不过有一个逻辑需要特别处理一下，就是要在每个单词之间加上空格（首单词除外）——判断逻辑可以表示为
if(slow!=0) s[slow++]=' ';
这样就可以做到在每个单词之间加上空格，并且去除首字母前面的空格了。
具体函数实现的代码如下：

1.         //去除字符串中多余的空格
2.         void removeExtraSpaces(string& s)
3.         {
4.                 int fast = 0, slow = 0;
5.                 for (fast = 0; fast < s.size(); fast++) {
6.                         //快指针指向我们要保留的字符
7.                         if (s[fast] != ' ') {
8.                                 //将每个单词之间加上空格，首单词除外
9.                                 if (slow != 0) s[slow++] = ' ';
10.                                 //将单词中间的空格去除
11.                                 while (fast < s.size() && s[fast] != ' ') {
12.                                         s[slow++] = s[fast++];
13.                                 }
14.                         }
15.                 }
16.                 s.resize(slow);
17.         }

复制代码

其余两个步骤的代码比较简单，我在这里就不过多赘述了
具体可以编译运行的代码如下：

[code]class Solution {public:        //反转字符串中的某段        void reverse(string& s, int start, int end)        {                for (int i = start, j = end; i < j; i++, j--) {                        swap(s, s[j]);                }        }        //去除字符串中多余的空格
        void removeExtraSpaces(string& s)
        {
                int fast = 0, slow = 0;
                for (fast = 0; fast < s.size(); fast++) {
                        //快指针指向我们要保留的字符
                        if (s[fast] != ' ') {
                                //将每个单词之间加上空格，首单词除外
                                if (slow != 0) s[slow++] = ' ';
                                //将单词中间的空格去除
                                while (fast < s.size() && s[fast] != ' ') {
                                        s[slow++] = s[fast++];
                                }
                        }
                }
                s.resize(slow);
        }        string reverseWords(string& s)        {                //移除字符串中多余的空格                removeExtraSpaces(s);                //反转这个字符串                reverse(s, 0, s.size() - 1);                //反转这个字符串中的每一个单词                int start = 0;                for (int i = 0; i