字符串day8

151 反转字符串中的单词

三个步骤
1、清除掉所有额外的空格，使用快慢指针方法
2、反转一整个字符串
3、根据空格，将空格之间的单词再反转

class Solution{
public:
    void reverse(string& s,int start,int end){  //倒序start和end之间闭区间的字符串
        for (int i=start,j=end;i<j;i++,j--){
            swap(s[i],s[j]);
        }
    }
    void removeExtraSpaces(string& s){//去除全部空格，在单词之间加上空格,使用快慢指针法
        int slow=0;
        for(int i=0;i<s.size();++i){
            if(s[i]!=' '){//快指针遇到非空格，也就是说遇到单词了
                if(slow!=0)s[slow++]=' ';//slow!=0说明不是首单词，需要加上一个空格，如果开头有空格那么并不需要处理
                while(i<s.size()&&s[i]!=' '){  //快慢指针，将slow的位置复制上fast的字符，直到空格为止
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow); //截断(包括resize)
    }
    string reverseWords(string s){
        removeExtraSpaces(s);
        reverse(s,0,s.size()-1);
        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;
    }
};

右旋字符串

思路就是 通过 整体倒叙，把两段子串顺序颠倒，两个段子串里的的字符在倒叙一把，负负得正，

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    int n;
    string s;
    cin >> n;
    cin >> s;
    int len = s.size(); //获取长度

    reverse(s.begin(), s.end()); // 整体反转
    reverse(s.begin(), s.begin() + n); // 先反转前一段，长度n
    reverse(s.begin() + n, s.end()); // 再反转后一段

    cout << s << endl;

}

28 实现strStr()

重点，需要理解KMP算法