其实字符串有很多语言都有它的函数库，但是还是不要用那些函数库对自己的基础不好；
//有些时候改用还是得用啊
class Solution {
public:
void reverseString(vector<char>& s) {
for(int i=0,j=s.size()-1;i<s.size()/2;i++,j--){
swap(s[i],s[j]);
}
}
};class Solution {
public:
int counts=0;
string reverseStr(string s, int k) {
int i;
for(i=0;i<s.size();i+=2*k)
{
if(i+k<s.size()){
reverse(s.begin()+i,s.begin()+k+i);
continue;//接着进行上述循环；
}//存在k个值就将他们全部反转
reverse(s.begin()+i,s.begin()+s.size());//如果没有k个值就将他们全部反转；
}
return s;
}
};//有一点难度的注意就是每次跳跃2*k并且最后不足只可能出现在最后结尾
其实这个函数reverse我们可以用第一题的算法来实现了可以实现
void reverseString(vector<char>& s，int start,int end) {
for(int i=start,j=end;i<j;i++,j--){
swap(s[i],s[j]);
}
}std::string 的输出是根据记录的长度而不是 '\0' 来判断结束的,想对string一个字符一个字符的复制，只能+=,不能a[i]=b[i]；
自己写的：
class Solution {
public:
string replaceSpace(string s) {
string str;
for(int i=0;i<s.size();i++){
if(s[i]==' '){
str+="%20";
}
else{
str+=s[i];
}
}
return str;
}
};
空间用得太多想要节约空间的话：
class Solution {
public:
string replaceSpace(string s) {
int count = 0; // 统计空格的个数
int sOldSize = s.size();
for (int i = 0; i < s.size(); i++) {
if (s[i] == ' ') {
count++;
}
}
// 扩充字符串s的大小，也就是每个空格替换成"%20"之后的大小
s.resize(s.size() + count * 2);//增添string容器的容量；
int sNewSize = s.size();//新的容器长度
// 从后先前将空格替换为"%20"
for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
if (s[j] != ' ') {
s[i] = s[j];//在同一个string中可以这么复制不同string中不可这么赋值
} else {
s[i] = '0';
s[i - 1] = '2';
s[i - 2] = '%';
i -= 2;
}
}
return s;
}
};
//后续会接着更的
class Solution {
public:
string reverseLeftWords(string s, int n) {
string str;
for(int i=n;i<s.size();i++){
str+=s[i];
}
for(int i=0;i<n;i++){
str+=s[i];
}
return str;
}
};自己写的比较简单浪费了空间
大佬的思想比较好
这道题目也非常类似，依然可以通过局部反转+整体反转 达到左旋转的目的。
具体步骤为：
- 反转区间为前n的子串
- 反转区间为n到末尾的子串
- 反转整个字符串
最后就可以得到左旋n的目的，而不用定义新的字符串，完全在本串上操作。
例如 ：示例1中 输入：字符串abcdefg，n=2
如图：
最终得到左旋2个单元的字符串：cdefgab
//代码随想录
class Solution {
public:
string reverseLeftWords(string s, int n) {
reverse(s.begin(),s.begin()+n);
reverse(s.begin()+n,s.end());
reverse(s.begin(),s.end());
return s;
}
};这kmp算法可真恶心啊
没看懂明天接着看今天不是很想刷题/(ㄒoㄒ)/~~
KMP算法主要应用在字符串匹配上。
KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
next数组就是一个前缀表（prefix table）。
前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。
字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
前缀表要求的就是相同前后缀的长度
kmp算法的时间复杂度：
n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)，之前还要单独生成next数组，时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(n+m)的。
这些我在数据结构都学过嘿嘿有手就行（手动狗头）
当期前缀和后缀有多少个相等前缀表的值就为多少
构造next数组：（我不理解了这东西很难）
void getNext(int* next, const string& s) {
int j = 0;
next[0] = 0;
for(int i = 1; i < s.size(); i++) {//不相等时j回溯回到他的上一个next对应的值
while (j > 0 && s[i] != s[j]) { // j要保证大于0，因为下面有取j-1作为数组下标的操作
j = next[j - 1]; // 注意这里，是要找前一位的对应的回退位置了
}
if (s[i] == s[j]) {//找到相同的前后缀
j++;
}
next[i] = j;//
}
}整个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[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;
}
int next[needle.size()];
getNext(next, 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;
}
};具体思想是利用next数组找到s中最长的重复部分让串减去得到一个周期的长度取余
是否为0最长长度就是在next数组的最后一位这样得到的前缀和后缀相同部分最多
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;
}
}
bool repeatedSubstringPattern(string s) {
if(s.size()==0){
return false;
}
int next[s.size()];
getNext(next,s);
int length=s.size();
if(next[length-1]!=0&&(length%(length-next[length-1]))==0){
return true;
}
return false;
}
};