题目

思路

题目的难点在于首先要清除多余的空格，并且单词之间要留一个空格，首单词前和末尾单词后不能有多余空格。我们使用双指针去除所有的空格，然后在处理完一个单词后手动加一个单词。具体思路是当快指针不等于空格时，赋值给慢指针，然后快慢指针同时移动，当快指针等于空格时，慢指针不动，快指针循环移动，一直循环到不等于空格时，继续上述操作。每当处理完一个单词，此时慢指针手动加一个空格，已满足每个单词之间要有一个空格的要求。判断slow != 0，是因为开头有可能有多余的空格，此时不需要额外添加。

其次需要翻转，我们首先将s所有的字符整体翻转过来，然后逐个翻转单词。注意s的范围在0-s.size-1,而s.size()为\0。最后的for循环到s.size()是为了知道到末尾了，方便翻转最后一个单词。

代码

class Solution {
public://翻转函数void reverse (string& s, int x, int y) {for (int i = x, j = y; i < j; i++, j--) {swap(s[i], s[j]);}}//删除多余的空格void deleteExtraSpaces (string& s) {//双指针法删除多余空格int slow = 0;for (int 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) {deleteExtraSpaces(s);reverse(s, 0, s.size() - 1);int start = 0;for (int i = 0; i <= s.size(); i++) {//对每个单词翻转,到达空格或者串尾，说明一个单词结束。if (s[i] == ' ' || i == s.size()) {reverse(s, start, i - 1);//下一个单词开始为i+1start = i + 1;}}return s;}
};