昨日回顾

• 字符串没有特殊内容，就是解决实际问题。
• 双指针yyds

151.翻转字符串里的单词

卡哥文字以及视频讲解链接

重点

• 第一步，移除多余空格
• 第二步，将整个字符串反转
• 第三步，将每个单词反转

解法思路

1. 移除多余空格。开头空格，单词间超过一个的空格，字符串最后一个单词后的空格，统统不要。
   我的思路是：快慢两个指针。快指针首先从0下标移动到第一个不是空格的下标。进入循环，快慢指针同时移动，单词字母全留下。快指针遇到空格，单独移动，空格全部直接跳过。同时在单词后使用慢指针给每一个单词后补一个空格。到了最后一个单词结尾补过空格后，循环结束。而补空格的位置是下标slow，直接 resize（slow），修改后的字符串大小就是slow，下标最后一位就是slow - 1。
2. 因为之前有实现reverse函数，我直接使用了STL库函数。库函数是左闭右开。
3. 仍是遍历，遇到空格，反转，遇到空格，反转，到达结尾，剩余反转。最后还是防止越界。
4. 字符串是很实际的生活工作场景，比较繁琐，但是整体实现，很有必要。

• 在移除空格后还有使用库函数splite的方式，将单词通过空格分隔放入字符串数组内，再倒序放入新字符串即可。也可以手动将单词一个一个放入一个栈内，再放入另一个栈，再放入新字符串。这两种方法是一种思路。但没法实现原地反转，没法使空间复杂度缩小到常数。

c++实现

class Solution {
public:
    void removeSpace(string& s){
        int slow = 0;
        int fast = 0;
        //处理字符串中第一个单词前的空格
        while(fast < s.size() && s[fast] == ' '){
            fast++;
        }
        //处理字符串单词间的空格
        while(fast < s.size()){
        	 	 //这个if是禁止下标0，初次进入循环也同样移动
            if(slow > 0){//这个if先跳过，看过下面代码再回头看
                slow++; //因为 s[slow] = ' '; 没有移动，在这里补一步移动
            }
            //循环内的第一个while，是同时从一个单词头移动到单词尾
            while(fast < s.size() && s[fast] != ' '){
            //while中首先判断fast < s.size()很有必要，不是多余步骤
            //防止最后一个单词后没有空格直接结束时，函数体内的s[fast++]出现越界
                s[slow++] = s[fast++];
            }
            //在每一个单词后补一个空格
            s[slow] = ' ';
            //将一个单词后的空格移动干净，找到下一个单词
            while(fast < s.size() && s[fast] == ' '){
                fast++;
            }
        }
        s.resize(slow);
        //这里为什么使用slow?肯定有读者第一次看认为应该是slow - 1
        //在补充了最后一个空格后 s[slow] = ' '; 中的slow是下标。slow下标，size就是slow + 1。
        //而我们不要最后一个空格，直接slow，结果正合题意。
    }
    string reverseWords(string s) {
        removeSpace(s);
        reverse(s.begin(),s.end());
        int left = 0;
        int right = 0;
        while(right < s.size()){
            if(s[right] == ' '){
                reverse(s.begin() + left , s.begin() + right);
                right++;
                left = right;
            }//完成一组反转，移动到下一组开始位置
            while(right < s.size() && s[right] != ' '){
                right++;
            }//找到下一个右边界位置，因为库函数是左闭右开，所以右边界位置是元素为 ' ' 的下标
            if(right == s.size()){
                reverse(s.begin() + left, s.end());
            }//最后一个单词因为没有空格，单独处理
        }
        return s;
    }
};

卡哥关于去空格，使用的双指针代码

看了代码以后，思路是一样的，但是我的就比较冗余，把简化后的问题又复杂化了。所以还是贴在一块，供大家比对学习。（仅去空格代码）

void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
    int slow = 0;   //整体思想参考https://programmercarl.com/0027.移除元素.html
    for (int i = 0; i < s.size(); ++i) { //
        if (s[i] != ' ') { //遇到非空格就处理，即删除所有空格。
            if (slow != 0) s[slow++] = ' '; //手动控制空格，给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。
            while (i < s.size() && s[i] != ' ') { //补上该单词，遇到空格说明单词结束。
                s[slow++] = s[i++];
            }
        }
    }
    s.resize(slow); //slow的大小即为去除多余空格后的大小。
}

卡码网：55.右旋转字符串

卡哥文字以及视频讲解链接

重点

• 没有特别，就是第一眼可能懵。
• 右旋转，左旋转方法都一样，分清左右就好

c++实现

#include <iostream>
#include <string>
#include<algorithm>

int main(){
    int k = 0;
    std::string s;
    std::cin >> k;
    std::cin >> s;
    if(k > s.size()){
        return 1;
    }
    //右旋转
    reverse(s.begin(),s.end());
    reverse(s.begin(),s.begin() + k);
    reverse(s.begin() + k,s.end());
    std::cout << s << std::endl;

    return 0;
}

28.实现strStr()

卡哥文字以及视频讲解链接

重点

• KMP
• 先去看KMP的具体实现。前缀表是什么？如何用代码实现？
• 前后缀比对的时候，都是从左往右一依次比对（有时候就是这里卡着没理解）。

c++实现

class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = -1;
        next[0] = j;
        for(int i = 1; i < s.size(); i++) { // 注意i从1开始
            while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
                j = next[j]; // 向前回退
            }
            if (s[i] == s[j + 1]) { // 找到相同的前后缀
                j++;
            }
            next[i] = j; // 将j（前缀的长度）赋给next[i]
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
		vector<int> next(needle.size());
		getNext(&next[0], needle);
        int j = -1; // // 因为next数组里记录的起始位置为-1
        for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始
            while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
                j = next[j]; // j 寻找之前匹配的位置
            }
            if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
                j++; // i的增加在for循环里
            }
            if (j == (needle.size() - 1) ) { // 文本串s里出现了模式串t
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

459.重复的子字符串

卡哥文字以及视频讲解链接

重点

• 具体实现看讲解，很详细
• KMP实现也可行，实现起来就更复杂了

c++实现

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; // r
        return false;
    }
};

坚持就是胜利

日期	天次	题目
01-14	1	704、27、977
01-15	2	209、59 （+ 2）
01-16	3	203、707、206
01-17	4	24 、19、面试题 02.07 、142
01-18	5	总结 数组 、链表
01-19	6	242、349、202、1
01-20	7	454、383、15、18
01-21	8	344、541、卡码54
01-22	9	151、卡码55、28、459

• 第一天，搞定！
• 第二天，搞定！
• 第三天，搞定！
• 第四天，搞定！
• 第五天，搞定！
• 第六天，搞定！
• 第七天，搞定！
• 第八天，搞定！
• 第九天，KMP差点搞定，思路理清，代码还不能完全写出。

author

轩