力扣 151反转字符串中的单词

思路

单词前面有空格，后面有空格，中间有多余空格

1去掉多余空格

2全部翻转

3单词内部翻转

这里也用双指针，一个start,一个end,当end遇到空格(即一个单词的结尾）或者是到达字符串s的末尾时

reverse(s,start,end-1)

//去除空格逻辑，双指针
void removeEmpty(string &s)
{
    int slow = 0;
    for(int fast =0;fast<s.size();fast++)
{//这里容易遗忘的是for循环里大的逻辑是 s[fast] !=' ' 就是说跳过前面和中间的空格
    if(s[fast] ！=' ')
    {
        if(slow != 0)//已经有一个单词了，这时需要添加一个空格
        {
            s[slow++] = ' ';
        }
        //如果遇到单词，将fast指针的部分复制到slow指针位置
        while(fast<s.size() && s[fast] != ' ')
        {
            s[slow++] = s[fast++];
        }
    }
}
s.resize(slow);
}

//整体逻辑，先翻转，再去空格，再单词内部翻转
string reverseWords(string s)
{
    reverse(s,0,s.size()-1);
    removeEmpty(s);
    int start=0;
    for(int i = 0;i<=s.size();i++)
    {
        if(i == s.size() ||s[i] ==' ')
        {
            reverse(s,start,i-1);
            start = i+1;
        }
    }
    return s;
}

整体代码如下 

// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem151.h"
 
using namespace std;
// @before-stub-for-debug-end
 
/*
 * @lc app=leetcode.cn id=151 lang=cpp
 *
 * [151] 反转字符串中的单词
 */
// @lc code=start
class Solution 
{
public:
//翻转逻辑
void reverse(string &s,int start,int end)
{
    while(start<end)
    {
        swap(s[start],s[end]);
        start++;
        end--;
    }
}
//去除空格
 
void removeEmpty(string &s)
{
    //双指针
    int slow = 0;
    for(int fast = 0;fast<s.size();fast++)
    {
        if(s[fast]!=' ')
        {
            if(slow != 0)
            {
                s[slow++] = ' ';
            }
            while(s[fast]!= ' ' && fast<s.size())
            {
                s[slow++] = s[fast++]; 
            }
        }
    }
    s.resize(slow);
}
//单词内部翻转
    string reverseWords(string s) {
        //先整体翻转，再去空格
        //再单词内部翻转,双指针
      
      reverse(s,0,s.size()-1);
      removeEmpty(s);
      int start = 0;
      for(int i = 0;i<=s.size();i++)
      {
        if(s[i] == ' '|| i == s.size())
        {
            reverse(s,start,i-1);
            start = i+1;
        }
      }
      return s;
 
    }
};
// @lc code=end