当前位置：首页 > article >正文

代码随想录算法训练营Day09 | 151.翻转字符串里的单词、卡码网：55.右旋转字符串、28. 实现 strStr()、459.重复的子字符串

article 2024/10/25 23:26:23

文章目录

151.翻转字符串里的单词
- 思路与重点
卡码网：55.右旋转字符串
- 思路与重点
28. 实现 strStr()
- 思路与重点
459.重复的子字符串
- 思路与重点
字符串总结和双指针总结

151.翻转字符串里的单词

题目链接：151. 反转字符串中的单词 - 力扣（LeetCode）
讲解链接：代码随想录 (programmercarl.com)
状态：直接看题解了。

思路与重点

可以用C++的stringstream对象来解决，

class Solution {
public:
    string reverseWords(string s) {
        istringstream iss(s);
        string ans;
        string word;
        while (iss >> word) {
                ans = word + " " + ans;
        }
        return ans.substr(0, ans.size() - 1);
    }
};

考虑使用 O(1) 额外空间复杂度的原地解法。解题思路如下：1. 移除多余空格。2. 将整个字符串反转。3.将每个单词反转。

class Solution {
public:
    void reverse(string& s, int start, int end){ //翻转，区间写法：左闭右闭 []
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }

    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的大小即为去除多余空格后的大小。
    }

    string reverseWords(string s) {
        removeExtraSpaces(s); //去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。
        reverse(s, 0, s.size() - 1);
        int start = 0; //removeExtraSpaces后保证第一个单词的开始下标一定是0。
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') { //到达空格或者串尾，说明一个单词结束。进行翻转。
                reverse(s, start, i - 1); //翻转，注意是左闭右闭 []的翻转。
                start = i + 1; //更新下一个单词的开始下标start
            }
        }
        return s;
    }
};

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

题目链接：55. 右旋字符串（第八期模拟笔试） (kamacoder.com)
讲解链接：代码随想录 (programmercarl.com)
状态：一次AC。

思路与重点

整体倒叙，把两段子串顺序颠倒，两个段子串里的的字符再倒叙一次，负负得正，这样就不影响子串里面字符的顺序了。

// 版本一
#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()

题目链接：28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）
讲解链接：代码随想录 (programmercarl.com)
状态：暴力法一遍AC。

思路与重点

暴力解法很简单：

class Solution {
public:
    int strStr(string haystack, string needle) {
        int haystackLen = haystack.size();
        int needleLen = needle.size();
        if(needleLen > haystackLen) return -1;
        for(int i = 0; i + needleLen <= haystackLen; i++){
            if(haystack[i] == needle[0]){
                if(haystack.substr(i, needleLen) == needle) return i;
            }
        }
        return -1;
    }
};

学习一下KMP算法，KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
长度为前1个字符的子串<font style="color:rgb(71, 101, 130);">a</font>，最长相同前后缀的长度为0。（注意字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
其中n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)，之前还要单独生成next数组，时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(n+m)的。暴力的解法显而易见是O(n × m)，所以KMP在字符串匹配中极大地提高了搜索的效率。
KMP算法的前缀next数组最通俗的解释，如果看不懂我也没辙了-CSDN博客：讲的是真好啊！！！

class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        vector<int> next(needle.size());
        getNext(&next[0], needle);
        int j = 0;
        for (int i = 0; i < haystack.size(); i++) {
            while(j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == needle.size() ) {
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

459.重复的子字符串

题目链接：459. 重复的子字符串 - 力扣（LeetCode）
讲解链接：代码随想录 (programmercarl.com)
状态：直接看题解了。

思路与重点

方法一：判断字符串s是否由重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成。（当然，我们在判断 s + s 拼接的字符串里是否出现一个s的的时候，要刨除 s + s 的首字符和尾字符，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s。）

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

方法二：需要证明当最长相等前后缀不包含的子串的长度可以被字符串s的长度整除，那么不包含的子串就是s的最小重复子串。

class Solution {
public:
    void getNext (int* next, const string& s){
        next[0] = 0;
        int j = 0;
        for(int i = 1;i < s.size(); i++){
            while(j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if(s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }
    bool repeatedSubstringPattern (string s) {
        if (s.size() == 0) {
            return false;
        }
        int next[s.size()];
        getNext(next, s);
        int len = s.size();
        if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
            return true;
        }
        return false;
    }
};