1、151翻转字符串里的单词

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

我的思路： 首先这道题返回一个新串，不要求在原串上修改，所以简便很多。直接一个每个区域用双指针填充就可以。

// 我的。。比较水的解法。。。
class Solution {
public:
    string reverseWords(string s) {
        string res;
        int low = s.size()-1,fast = low;

        while(fast>=0){
            while(fast>=0 && s[fast]==' '){
                fast--;
            };
            low = fast;
            while(fast>=0 && s[fast]!=' '){
                fast--;
            }
            res.append(s,fast+1,low-fast);
            res+=" ";
        }
        while(res.back()==' '){
            res.pop_back();
        }
        return res;
    }
};

代码随想录： 分隔单词，然后定义一个新的string字符串，最后再把单词倒序相加，那么这道题题目就是一道水题了，失去了它的意义。

提升：不要使用辅助空间，空间复杂度要求为O(1)。

方法： "the sky is blue "

移除多余空格："the sky is blue" 对应27移除元素
字符串反转："eulb si yks eht"对应344反转字符串
单词反转："blue is sky the"对应541反转字符串II

// 看了代码随想录后我写的
// 可以直接当模板拿来写
class Solution {
public:
    string reverseWords(string s) {
        // remove extra /0x20  移除连续重复的元素
        int low = 0,fast = 0;
        for(fast = 0;fast < s.size();fast++){
            if(s[fast]==' ' && (fast==0 || s[fast-1]==' '))continue;
            s[low++] = s[fast];
        }
        int length = s[low-1]==' '?low-1:low;  //最后可能有空格，长度需要-1

        // str reverse   // 字符串逆序
        int left = 0,right = length-1;
        while(left < right){
            auto temp = s[right];
            s[right] = s[left];
            s[left] = temp;
            left++;
            right--;
        }

        // word reverse   //单词逆序
        int p = 0;
        while(p < length){
            left = p;
            while(p < length && s[p]!= ' ')p++;
            right = p-1;
            while(left < right){
                auto temp = s[right];
                s[right] = s[left];
                s[left] = temp;
                left++;
                right--;
            }
            p++;
        }
        return string(s,0,length);
    }
};

2、卡码网-55右旋转字符串

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。
例如，对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。

我的思路： 受前面一题151翻转字符串里的单词 的启发，可以先反转整个串，然后把对应的需要的部分反转。

tips： 反转字符串

#include <string>
#include <iostream>
using namespace std;

void reverse(string &str, int start, int end){
    int left = start, right = end;
    while(left < right){
        auto temp = str[right];
        str[right] = str[left];
        str[left] = temp;
        left++;
        right--;
    }
}

void rota(string &str,int k){
    // reverse 所有字符
    int left = 0,right = str.size()-1;
    reverse(str,left,right);
    
    //reverse 前k个字符
    left = 0,right = k-1;
    reverse(str,left,right);
    
    //reverse 剩下字符
    left = k,right = str.size()-1;
    reverse(str,left,right);
}

int main(){
    string str;
    int k = 0;
    cin >> k >> str;
    rota(str,k);
    cout << str;
}

3、28实现strStr()

二刷再做

4、459重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

我的思路： 使用for循环一个一个的匹配。看着简单，写起来还是有点发愣的，也用了30来分钟。O(n^2)复杂度。

代码随想录-移动匹配法： 如果s是一个重复子串，用 s + s，这样组成的字符串中，后面的子串做前串，前面的子串做后串，就一定还能组成一个s

// 我的暴力解法，leetcode通过了
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        for(int i = 1;i<=s.size()/2;i++){
            if(s.size()%i!=0)continue;
            int l = 0,r = l+i;
            while(r < s.size() && s[l]==s[r]){
                l++;
                r++;
                if(l >= i){
                    l=0;
                }
            }
            if(r == s.size())return true;
        } 
        return false;
    }
};

// 代码随想录
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string t = s + s;
        t.erase(t.begin()); t.erase(t.end() - 1); // 掐头去尾
        if (t.find(s) != std::string::npos) return true; // find调用库函数
        return false;
    }
};