题目描述

给定一个字符串，请将字符串中单词的顺序倒过来。

注意：
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个

希望你使用额外 $O(1)$ 的空间

样例

输入：”the sky is blue”,
输出：”blue is sky the”.

算法

数组翻转 $o(n)$

• 先以及局部翻转每个单词 eht yks si eulb
• 然后整体翻转字符串 blue is sky the

细节

• 每个单词之间可能存在多余的空格，结果中只保留一个
  • 找到每个单词
  • 翻转该单词后添加一个空格即可
• 前置多余空格的处理
  • 用k 来维护 翻转单词且压缩直接空格后字符串的下标
  • 把 K到末尾删除即可，删除的数前置多余的空格以及单词间多余的空格

模板

• 双指针维护一段区间

c++ 代码

class Solution {
public:
    string reverseWords(string s) {
        int  k = 0; 
        // k为 翻转每个单词，且压缩单词间空格后的下标
        // 所以最终一定小于等于字符串总长度
        for(int i = 0; i < s.size(); i++)
        {
            // 找到每个单词的起始位置
            while(i < s.size() && s[i] == ' ') i ++;
            if(i == s.size()) break;

            // 找到每个单词的结尾位置 并翻转单词
            int j = i;
            while(j < s.size() && s[j] != ' ') j++;
            reverse(s.begin() + i, s.begin() + j);

            // 翻转后人为添加一个空格  至少有一个单词时
            if(k) s[k ++] = ' ';

            // 把单词翻转后的结果在原字符串上原地修改
            while(i < j) s[k ++] = s[i ++];
            // while 结束的条件是 i = j 此时j指向的是空格，i ++ 指向下一个单词的开头或者空格 
        }

        //把后面没用位置删除即可
        s.erase(s.begin() + k , s.end()); // 左闭右开 区间
        reverse(s.begin(), s.end());

        return s;
    }
};