代码随想录day8

344.反转字符串

方法一：直接调用库函数

方法二：

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

当然交换逻辑直接用swap就可以了。

541. 反转字符串II

整段整段的跳就可以了，只对每一段前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);
                //剩余字符保持原样
                continue;
            }
            reverse(s.begin()+i,s.end());
        }
        return s;
    }
};

剑指Offer 05.替换空格

预先给数组进行扩容，然后从后向前对数组进行填充。

class Solution {
public:
    string replaceSpace(string s) {
        int cnt=0;
        int oldsize=s.size();
        for(int i=0;i<oldsize;i++){
            if(s[i]==' ') cnt++;
        }
        s.resize(oldsize+cnt*2);
        int newsize=s.size();
        for(int i=oldsize-1,j=newsize-1;i<j;i--,j--){
            if(s[i]!=' ') s[j]=s[i];
            else{
                s[j]='0';
                s[j-1]='2';
                s[j-2]='%';
                j-=2;
            }
        }
        return s;
    }
};

151.翻转字符串里的单词

双指针去除空格，之后先整体翻转，再翻转单词

class Solution {
public:
    void removespace(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) {
        removespace(s);
        reverse(s.begin(),s.end());
        int i=0,j=0;
        while(j<s.size()&&s[j]!=' '){
            j++;
        }
        reverse(s.begin()+i,s.begin()+j);
        for(i=j+1;j<=s.size();j++){
            if(s[j]==' '||j==s.size()){
                reverse(s.begin()+i,s.begin()+j);
                i=j+1;
            }
        }
        return s;
    }
};

错因：1、在单词前面加空格之后，满指针忘记移动

2、反转每个单词时忽略了一种情况，如果最后j指向结尾，也要进行翻转。

剑指Offer58-II.左旋转字符串

局部反转+整体翻转

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(),s.begin()+n);
        reverse(s.begin()+n,s.end());
        reverse(s.begin(),s.end());
        return s;
    }
};