Day09 | 字符串反转字符串&&反转字符串II&&反转字符串里的单词

代码随想录 | Day09 | 字符串：反转字符串&&反转字符串II&&反转字符串里的单词

主要学习内容：

1.双指针操作字符串

2.reverse函数的使用

344.反转字符串

可以调用reverse反转字符串函数

解法：双指针

class Solution {
public:
    void reverseString(vector<char>& s) 
    {
        for(int i=0;i<s.size()/2;i++)
            swap(s[i],s[s.size()-i-1]);
        /*
        for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {
            swap(s[i],s[j]);
            */
    }
};

541.反转字符串II

541. 反转字符串 II - 力扣（LeetCode）

思路：

大体逻辑相同

都是每隔2*k个字符就反转这一段的前k个字符

只需要注意到最后一段不足k个字符时需要全部反转即可

使用库函数版本

class Solution {
public:
    string reverseStr(string s, int k) 
    {
        for(int i=0;i<s.size();i+=2*k)
        {
            if(i+k<=s.size())
                reverse(s.begin()+i,s.begin()+i+k);
            else
            	reverse(s.begin()+i,s.end());
        }
        return s;
    }
};

不使用库函数版本

class Solution {
public:
    void r(string &s,int start,int end)
    {
        for(int l=start,r=end;l<r;l++,r--)
            swap(s[l],s[r]);
    }
    string reverseStr(string s, int k) 
    {
        for(int i=0;i<s.size();i=i+2*k)
        {
            if(i+k>s.size())
                r(s,i,s.size()-1);
            else
                r(s,i,k+i-1);
        }
        return s;
    }
};

151.反转字符串中的单词

151. 反转字符串中的单词 - 力扣（LeetCode）

解法：双指针

思路：

1.除去多余的空格（头，尾，中间）

2.整个字符串反转

3.单个单词反转

1.去除空格

快慢指针初始化：都是指向第一个元素

先去除头部的，等于空格的话快指针直接前移

去除中间的，不等于空格的时候快指针的值直接赋值给慢指针，等于空格的时候进行判断如果他的前一个也是空格那就不更新慢指针如果第一次碰到空格也要赋值给慢指针（就相当于进行了单词间的空格的保留操作）

最后去除尾部的

遍历到最后如果末尾有空格的话，s会在最后一个单词后面剩下一个空格，原来末尾没有的话就什么都不会剩下

另外一点是用resize而不是erase，erase操作时间复杂度太高了

void eraseSpaces(string &s)
{
    int r=0,l=0;
    while(s[r]==' ')
        r++;
    for(;r<s.size();r++)
    {
        if(s[r]==' '&&s[r]==s[r-1]&&(r-1>0))
            continue;
        else
            s[l++]=s[r];
    }   
    if(s[l-1]==' ')
        s.resize(l-1);
    else    
        s.resize(l);
}

如果做过移除元素的话会很熟悉

按照移除元素的做法写就是

把数组内所有的空格都移除掉

然后遍历到每个单词末尾时，自己在每个单词末尾加一个空格即可

代码如下

void eraseSpaces(string &s)
    {
        int l=0;
        for(int r=0;r<s.size();r++)
        {
            if(s[r]!=' ')//没有遇到空格
            {
                if(l!=0)//补空格的过程，慢指针已经指向了一个单词的末尾
                    s[l++]=' ';
                //快指针赋值给慢指针
                while(r<s.size()&&s[r]!=' ')
                    s[l++]=s[r++];
            }
        }
        s.resize(l);
    }

2.整个字符串反转就用reverse函数即可

3.单词反转

双指针，慢指针指向一个单词头，快指针指向单词尾后的空格，这样好利用reverse

慢指针start，快指针用循环因子i表示，只要快指针等于空格，那就说明快慢指针之间是一个完整单词那就反转该部分的单词，然后更新慢指针为下一单词的首个元素即i+1

特殊处理是快指针遍历到s.size()部分，后面没有空格不会处理，咱们自己加上这个条件就行

//整体代码
class Solution {
public:
    //1.删除空格
    void eraseSpaces(string &s)
    {
        int r=0,l=0;
        while(s[r]==' ')
            r++;
        for(;r<s.size();r++)
        {
            if(s[r]==' '&&s[r]==s[r-1]&&(r-1>0))
                continue;
            else
                s[l++]=s[r];
        }   
        if(s[l-1]==' ')
            s.resize(l-1);
        else    
            s.resize(l);
    }
    string reverseWords(string s) {
       eraseSpaces(s);
        //2.反转整个字符串
       reverse(s.begin(),s.end());
       int start=0;
       for(int i=0;i<=s.size();i++)
       {
           //反转每个单词
            if(s[i]==' '||i==s.size())
            {
                reverse(s.begin()+start,s.begin()+i);
                start=i+1;//更新慢指针
            }
       }
       return s;
    }
};

//一刷的时候自己写的，我也忘了自己咋写的了，反正是过了（苦笑）
class Solution {
public:
    string reverseWords(string s) {
        string res;
        bool flag=true;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]==' '&&flag)
            {
                res+=s[i];
                flag=false;
            }
            else   if(s[i]!=' ')
            {
                res+=s[i];
                flag=true;
            }
        }
        if(res[0]==' '&&res[res.size()-1]==' ')
        {
            string c(res.begin()+1,res.end()-1);
            s=c;
        }
        else if(res[0]==' '&&res[res.size()-1]!=' ')
        {
            string c(res.begin()+1,res.end());
            s=c;
        }
        else if(res[0]!=' '&&res[res.size()-1]==' ')
        {
            string c(res.begin(),res.end()-1);
            s=c;
        }
        else    
            s=res;
        reverse(s.begin(),s.end());
        int l=0;
        for(int i=0;i<=s.size();i++)
        {
            if(s[i]==' '||i==s.size())
            {
                reverse(s.begin()+l,s.begin()+i);
                l=i+1;
            }
        }
        return s;
    }
};