代码随想录第八天|151.翻转字符串里的单词 卡码网：55.右旋转字符串 28. 实现 strStr() 459.重复的子字符串

本文主要是介绍代码随想录第八天|151.翻转字符串里的单词 卡码网：55.右旋转字符串 28. 实现 strStr() 459.重复的子字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

反转字符串的单词

思路：刷过稍微忘记

class Solution {
public://去除空格string remove(string s){//使用快慢指针int slow=0;int i=0;for(;i<s.size();i++){if(s[i]!=' '){if(slow!=0){s[slow++]=' ';}while(s[i]!=' '&&i<s.size()){s[slow++]=s[i++];}}}s.resize(slow);return s;}string reverseWords(string s) {int slow=0,i=0;//slow代表单词开头 i代表结尾s=remove(s);reverse(s.begin(),s.end());int start=0;for(int i=0;i<=s.size();i++){if (i == s.size() || s[i] == ' '){reverse(s.begin()+start,s.begin()+i);start=i+1;}}return s;}
};

55. 右旋字符串（第八期模拟笔试）

思路:做过

#include<bits/stdc++.h>
using namespace std;
int main(){int d;string s;cin>>d>>s;reverse(s.begin(),s.end());reverse(s.begin(),s.begin()+d);reverse(s.begin()+d,s.end());cout<<s;return 0;
}

28. 实现 strStr()

思路：经典KMP 需要二刷 比之前熟练一点

class Solution {
public://最长前缀和vector<int> Next(string needle){vector<int> next(needle.size());int j=0;//最长前缀和next[0]=0;for(int i=1;i<needle.size();i++){while(j>0&&needle[i]!=needle[j]){j=next[j-1];//回退到下一个最长前缀和 若是0直接退出}if(needle[i]==needle[j])j++;next[i]=j;}return next;}int strStr(string haystack, string needle) {vector<int> next=Next(needle);int i=0,j=0;while(i<haystack.size()&&j<needle.size()){if(haystack[i]==needle[j]){i++;j++;}else{//不匹配 j回退if(j==0){i++;}else{//到前缀的下一个匹配j=next[j-1];}}}if(j==needle.size())return i-j;return -1;}
};

459.重复的字符串

思路：暴力 遍历结尾作为字串 然后在主串检查

KMP 和移动搜索需要二刷

class Solution {
public:bool repeatedSubstringPattern(string s) {string t=s+s;//如果字符串是循环子串 中间一定会搜索到相同字符串t.erase(t.begin());t.erase(t.end()-1);if(t.find(s)!=string::npos)return true;return false;}
};

KMP利用next数组和重复子串的性质 ：

数组长度-最大前缀和长度为一个周期 如果数组能整除这个周期说明是重复子串

这篇关于代码随想录第八天|151.翻转字符串里的单词 卡码网：55.右旋转字符串 28. 实现 strStr() 459.重复的子字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---