第八天
151.翻转字符串里的单词
字符串复杂操作拿捏了！ | LeetCode:151.翻转字符串里的单词_哔哩哔哩_bilibili
151.翻转字符串里的单词 | 代码随想录
笔记
怎么去掉多余空格？和数组删除元素那个很像，双指针遍历即可，但是中间涉及到要slow这个指针需要手动添加一个空格。
1.定义两个指针，fast指针遍历旧数组，slow指针遍历新数组，当fast碰到非空格的时候进行处理：将fast指向的值赋值给slow，直到再次遇上空格（说明这个单词已经处理完毕）
2.怎么手动添加空格？如果slow不是第一个，在处理下一个单词前在slow处加入空格
3.修改这个字符串的大小为slow
怎么反转？先把整个字符串反转，再一个单词一个单词进行反转
实操出现问题
reverse的用法：（注意：1.传入参数是迭代器 2.不是s.reverse()）
代码/比较
class Solution {
public:string delete_extra_space(string &s){//双指针删除空格int slow=0;for(int i=0;i<s.size();i++){if(s[i]!=' ')//碰到不是空格就处理{//人为在单词后面添加一个空格if(slow!=0)//slow！=0表示如果是开头的单词不予处理s[slow++]=' ';//把单词补上while(i<s.size()&&s[i]!=' ')//i要在范围内，碰到空格就停止，因为那是下一个单词了{s[slow++]=s[i++];}}}s.resize(slow);//return s;}string reverseWords(string s) {delete_extra_space(s);//去除多余空格reverse(s.begin(),s.end());//全部翻转一次//再逐个反转int begin=0;for(int i=0;i<=s.size();i++){if(i == s.size() || s[i] == ' ') //反转条件是碰到空格或者最后一个{reverse(s.begin() + begin, s.begin() + i);begin = i + 1;}}return s;}
};
55.右旋转字符串
右旋字符串 | 代码随想录
笔记：
反转的思路和上面的题目很像，先整体反转，再局部反转
实操出现的问题
无
代码/比较：
#include <iostream>
#include <algorithm>
using namespace std;
//不申请额外空间，只在原本的字符串上操作
int main()
{int k;string s;cin>>k;cin>>s; int len=s.size();//先整体反转reverse(s.begin(),s.end());//再局部反转reverse(s.begin(),s.begin()+k);reverse(s.begin()+k,s.end());cout<<s;
}
459.重复的子字符串
笔记：
kmp的前后缀：不包含第一个/最后一个字符的所有字串：字符串为ABCDS:前缀为[A,AB,ABC,ABCD] 后缀为[S,DS,CDS,BCDS]
kmp的next数组：初步理解，next数组就是告诉你在比较错误的时候，最远应该往哪个地方回退。
怎么求解next数组：i指向当前遍历的，j指向i-1之前的最大前缀末尾；如果j和i对应的数值相等，则对应的next[i-1]数值自增即可；如果不相等，是有可能存在更小的前后缀相同。
实操出现的问题：
感觉有点难，没有自己写一遍
代码/比较：
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;}
};
1