day08 反转字符串 反转字符串Ⅱ 替换数字 翻转字符串里的单词 右旋转字符串

题目1：344 反转字符串

题目链接：344 反转字符串

题意

字符串是数组的形式，使用O(1)的空间将字符串反转

双指针法

法一

代码

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

• 时间复杂度: O(n)
• 空间复杂度: O(1)

法二

代码

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0;
        int right = s.size()-1;
        while(left<=s.size() && right>=0 && right>left){
            swap(s[left],s[right]);
            left++;
            right--;
        }
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)

延伸（swap的实现）

法一（使用中间变量temp）

int temp = s[i];
s[i] = s[j];
s[j] = temp;

法二（使用位运算）异或交换法

//开始s[i]==a  s[j]==b
s[i]^=s[j];  //s[i]=a^b   a异或b
s[j]^=s[i];  //s[j]=b^(a^b)=a
s[i]^=s[j];  //s[i]=a^(a^b)=b
//最终s[i]==b  s[j]==a

题目2：反转字符串Ⅱ

题目链接：541 反转字符串Ⅱ

题意

字符串s每计数至2k个字符，就反转这2k个字符的前k个字符；

剩余字符少于k个，就将剩余字符全部反转；如果剩余字符大于等于k个且小于2k个，反转前k个字符

巧妙解法

i+=(2*k)，i每次移动2k个距离

代码

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);
               continue;//继续寻找下一组
           }
           reverse(s.begin()+i,s.end());
       }
       return s;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)

代码

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;
    }
};

题目3：54 替换数字

题目链接：54 替换数字

题意

字符串s（包含小写字母和数字字符）将数字字符替换位number，字母不变

不能简单地遇到数字就将其替换位number，因为数字是1个字符，而number是6个字符，直接替换的话，大小不对等，需要扩充大小

双指针

i指向新串的末尾，j指向旧串的末尾，从后向前遍历

详细的遍历过程

逻辑问题

例1：for循环中j<i? ?为啥j不能小于等于i呢？

原因

例2 为啥i，j要从后往前遍历，从前向后遍历不行嘛？

从前向后遍历的话，遇到数字字符，就需要将该数字字符后面的字符向后移动5个格，然后才可以填充number，时间复杂度是O(n^2)

代码

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int main(){
    string s;
    cin>>s;
    int count = 0;
    int oldsize = s.size();
    for(int i=0;i<s.size();i++){
        if(s[i]>='0'&& s[i]<='9'){
            count++;
        }
    }
    s.resize(s.size()+count * 5);
    int newsize = s.size();
    for(int i=newsize-1,j=oldsize-1;j<i;i--,j--){
        if(s[j]>='a'&&s[j]<='z'){
            s[i]=s[j];
        }
        else{
            s[i] = 'r';
            s[i-1] = 'e';
            s[i-2] = 'b';
            s[i-3] = 'm';
            s[i-4] = 'u';
            s[i-5] = 'n';
            i -= 5;
        }
    }
    cout<<s<<endl;
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

题目4：151 反转字符串里的单词

题目链接：151 反转字符串中的单词

题意

反转字符串s中单词的顺序? ?输入的字符串的开头或结尾可能会存在多个空格，单词与单词之间可能也存在多个空格

反转字符串时，仅仅在单词与单词之间有1个空格?

关键是字符串去除空格的逻辑，反转的逻辑：整体反转+局部反转

双指针（删除多余空格）

fast指向单词，slow指向单词所在的新的位置??

添加空格

在每个单词移动之前，添加一个空格，第一个单词除外

实例

代码

class Solution {
public:
    string reverseWords(string s) {
        //1 移除多余空格
        int slow = 0;
        for(int fast=0;fast<s.size();fast++){
            if(s[fast]!=' '){//找到了单词
                //单词前添加一个空格
                if(slow!=0){
                    s[slow] = ' ';
                    slow++;
                }
                //将单词移动到新的位置
                while(fast<s.size() && s[fast]!=' '){
                    s[slow] = s[fast];
                    slow++;
                    fast++;
                }  
            }
        }
        s.resize(slow);
        //2 反转单词
        //①整体反转
        reverse(s.begin(),s.end());//左闭右开
        //②单词反转
        int start = 0;
        for(int i=0;i<=s.size();i++){//reverse左闭右开
            if(s[i]==' ' || i==s.size()){//每个单词后有空格，最后一个单词后没空格
                reverse(s.begin()+start,s.begin()+i);//reverse左闭右开
                start = i + 1;
            }
        }
        return s;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)?

一般思路（分3种情况讨论）

字符串前有空格? 字符串中有多余空格? ? 字符串后有多余空格

代码

class Solution {
public:
    void removespace(string& s){
        int slow = 0;
        int fast = 0;
        //去掉前面的空格,寻找有效的字符,持续过程,开头可能有多个空格
        while(fast<s.size()&&s[fast]==' '){
            fast++;
        }
        //去掉中间多余的空格,如果原字符串末尾有空格的话，会使得末尾有1个空格
        for(;fast<s.size();fast++){//使用fast+1的话，fast+1可能会越界
            if(fast-1>0 && s[fast]==s[fast-1] && s[fast]==' '){
                continue;
            }
            else{//不是空格时，直接将fast位置处的值赋值给slow，然后slow向后移动一个位置
                s[slow] = s[fast];
                slow++;}
        }
        //去掉末尾的1个空格，因为上述代码的slow++了，slow会移动到多一个位置的地方，所以判断slow-1
        if(slow-1>0&&s[slow-1]==' '){
            s.resize(slow-1);
        }
        else{//原字符串末尾没有空格
            s.resize(slow);
        }
    }
    string reverseWords(string s) {
        removespace(s);//去除字符串中多余的空格
        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;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)?

题目5：55? 右旋转字符串

题目链接：55 右旋转字符串

题意

将字符串s后面的k个字符移到字符串的前面，实现右旋转操作

整体反转+局部反转

代码

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    string s;
    int k;
    cin>>k;
    cin>>s;
    //整体反转
    reverse(s.begin(),s.end());
    //局部反转
    reverse(s.begin(),s.begin()+k);
    reverse(s.begin()+k,s.end());
    cout<<s<<endl;
}

局部反转+整体反转

代码

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    string s;
    int k;
    cin>>k;
    cin>>s;
    //整体反转
    reverse(s.begin(),s.begin()+s.size()-k);
    //局部反转
    reverse(s.begin()+s.size()-k,s.end());
    reverse(s.begin(),s.end());
    cout<<s<<endl;
}