151.翻转字符串里的单词
题目链接：151.翻转字符串里的单词
文档讲解：代码随想录
状态：复杂空间AC，学习了不额外空间做法
思路
我的思路：从后向前遍历，将每个单词加入result新字符串中，并且手动添加空格分隔，缺点：浪费空间
难度提升：不要使用辅助空间，空间复杂度要求为O(1)
去除空格：快慢指针法，思路类似于27.移除元素，慢指针配合resize重新构造数组
最后使用reverse反转整体与各个单词
本题学习了单序列内部操作的细节（快慢指针，如何分割），以及反转函数reverse在整体与细节的妙用
题解
class Solution {
public:
void wash(string &s)
{
int fast = 0, slow = 0;
while(fast<s.size()-1 && s[fast] == ' ')fast++;//去前面空格
while(fast<s.size())//去中间冗余空格
{
if(s[fast]!=' ')s[slow++] = s[fast++];
else if(fast>0 && s[fast] == ' ' && s[fast-1] != ' ')s[slow++] = s[fast++];
else fast++;
}
if(s[slow-1] == ' ')s.resize(slow-1);//去尾部空格
else s.resize(slow);
}
void reverse(string &s, int begin, int end)
{
int left = begin, right = end;
while(left<right)swap(s[left++],s[right--]);
}
string reverseWords(string s) {
// string temp("");
// for(int i = s.size()-1;i>=0;i--)
// {
// if((i>0 && s[i]!=' ' && s[i-1] == ' ')||(i == 0 && s[i]!=' '))
// {
// int j = i;
// while(j<s.size() && s[j]!=' ')
// {
// temp += s[j++];
// }
// temp += ' ';
// }
// }
// string result(temp.begin(),temp.end()-1);
wash(s);
reverse(s,0,s.size()-1);
int start = 0;
for(int i = 0;i<s.size();i++)
{
if(s[i] == ' ')
{
reverse(s,start,i-1);
start = i+1;
}
if(i == s.size()-1)reverse(s,start,i);
}
return s;
}
};
55.右旋转字符串
题目链接：55.右旋转字符串
文档讲解：代码随想录
状态：复杂空间轻松AC，瞥一眼思路单空间AC思路
我的思路：拼接，十分狼狈的拼接
右旋左旋->可以转化为局部与个体的反转组合，学习到了很简单的思考方向
题解
#include <iostream>
#include <string>
using namespace std;
void reverse(string &s ,int begin, int end)
{
int left = 0,right = s.size()-1;
while(left<right)swap(s[left++],s[right--]);
}
int main()
{
// int k = 0;
// string s("");
// cin>>k>>s;
// string result(s.end()-k,s.end());
// result += string(s.begin(),s.end()-k);
// cout<<result<<endl;
int k = 0;
string s("");
cin>>k>>s;
reverse(s,0,s.size()-1-k);
reverse(s,s.size()-k,s.size()-1);
reverse(s,0,s.size()-1);
cout<<s<<endl;
return 0;
}
28.实现strStr()
题目链接：28.实现strStr()
文档讲解：代码随想录
状态：不会，学习KMP算法
思路
KMP算法正确性的证明：反证法
KMP算法要点：利用最长前后缀减少文本串指针的回溯，减低算法复杂度
前缀：指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀：指不包含第一个字符的所有以最后一个字符结尾的连续子串。
next数组构造与主函数搜索：关键思想都是一个，即两个串的匹配与模式串的回溯问题
KMP关键思想图解：
题解
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[j]!=s[i])
{
j = next[j-1];
}
if(s[i] == s[j])j++;
next[i] = j;
}
}
int strStr(string haystack, string needle) {
vector<int> next(needle.size(),0);
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-j+1;
}
return -1;
}
};
459.重复的子字符串
题目链接：459.重复的子字符串
文档讲解：代码随想录
状态：不会，证明比较难
思路
暴力法：第一层for循环遍历子字符串个数，第二层for循环确定是否为字串循环
关键细节在于，第一层for遍历子串，因为若重复则s[0]一定为子串起始；第二次判断细节：循环性，即周期性s[j] != s[j-i]、还要注意是否最后一个循环完整s.size()%i != 0
移动匹配方法、KMP解法（最长前后缀字串）证明方式见：春水煎茶 、代码随想录
题解
class Solution {
public:
void getNext(int *next, const string &s)
{
int j = 0;
next[j] = 0;
for(int i = 1;i<s.size();i++)
{
while(j>0 && s[j]!=s[i])j = next[j-1];
if(s[j]==s[i])j++;
next[i] = j;
}
}
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;
// for(int i = 1;i<=s.size()/2;i++)
// {
// if(s.size()%i != 0)continue;
// int j = i;
// while(j<s.size())
// {
// if(s[j] != s[j-i])break;
// j++;
// if(j == s.size())return true;
// }
// }
// return false;
vector<int> next(s.size());
getNext(&next[0], s);
if(next[s.size()-1]!=0 && s.size()%(s.size()-next[s.size()-1]) == 0)return true;
return false;
}
};
字符串总结
针对字符串的一些常用方法：如s.find() == string::npos、t.erase(t.begin())与其他数据结构的区别
字符串算法操作不多，反转可以玩出花、KMP算法及其应用要掌握
在C++中，find函数有两种主要用途：用于字符串和容器的查找。对于字符串，使用的是成员函数std::string::find；而对于容器（如std::vector或std::list），则需要借助标准库中的算法std::find。
字符串查找：通过std::string::find可以定位子字符串或字符的位置，返回值为size_t类型，若未找到则返回std::string::npos。
容器查找：容器本身没有成员函数find，需要通过std::find实现，返回指向目标元素的迭代器，若未找到则返回尾后迭代器end()。