算法训练营第九天：字符串进阶

算法训练营第九天|字符串续

• 昨日回顾
• 151.翻转字符串里的单词
• • 卡哥文字以及视频讲解链接
  • • 重点
    • 解法思路
    • c++实现
    • 卡哥关于去空格，使用的双指针代码
• 卡码网：55.右旋转字符串
• • 卡哥文字以及视频讲解链接
  • • 重点
    • c++实现
• 28.实现strStr()
• • 卡哥文字以及视频讲解链接
  • • 重点
    • c++实现
• 459.重复的子字符串
• • 卡哥文字以及视频讲解链接
  • • 重点
    • c++实现
• 坚持就是胜利

昨日回顾

• 字符串没有特殊内容，就是解决实际问题。
• 双指针yyds

151.翻转字符串里的单词

卡哥文字以及视频讲解链接

重点

• 第一步，移除多余空格
• 第二步，将整个字符串反转
• 第三步，将每个单词反转

解法思路

• 在移除空格后还有使用库函数splite的方式，将单词通过空格分隔放入字符串数组内，再倒序放入新字符串即可。也可以手动将单词一个一个放入一个栈内，再放入另一个栈，再放入新字符串。这两种方法是一种思路。但没法实现原地反转，没法使空间复杂度缩小到常数。

c++实现

class Solution {
public:
void removeSpace(string& s){
int slow = 0;
int fast = 0;
//处理字符串中第一个单词前的空格
while(fast < s.size() && s[fast] == ' '){
fast++;
}
//处理字符串单词间的空格
while(fast < s.size()){
//这个if是禁止下标0，初次进入循环也同样移动
if(slow > 0){//这个if先跳过，看过下面代码再回头看
slow++; //因为 s[slow] = ' '; 没有移动，在这里补一步移动
}
//循环内的第一个while，是同时从一个单词头移动到单词尾
while(fast < s.size() && s[fast] != ' '){
//while中首先判断fast < s.size()很有必要，不是多余步骤
//防止最后一个单词后没有空格直接结束时，函数体内的s[fast++]出现越界
s[slow++] = s[fast++];
}
//在每一个单词后补一个空格
s[slow] = ' ';
//将一个单词后的空格移动干净，找到下一个单词
while(fast < s.size() && s[fast] == ' '){
fast++;
}
}
s.resize(slow);
//这里为什么使用slow?肯定有读者第一次看认为应该是slow – 1
//在补充了最后一个空格后 s[slow] = ' '; 中的slow是下标。slow下标，size就是slow + 1。
//而我们不要最后一个空格，直接slow，结果正合题意。
}
string reverseWords(string s) {
removeSpace(s);
reverse(s.begin(),s.end());
int left = 0;
int right = 0;
while(right < s.size()){
if(s[right] == ' '){
reverse(s.begin() + left , s.begin() + right);
right++;
left = right;
}//完成一组反转，移动到下一组开始位置
while(right < s.size() && s[right] != ' '){
right++;
}//找到下一个右边界位置，因为库函数是左闭右开，所以右边界位置是元素为 ' ' 的下标
if(right == s.size()){
reverse(s.begin() + left, s.end());
}//最后一个单词因为没有空格，单独处理
}
return s;
}
};

卡哥关于去空格，使用的双指针代码

看了代码以后，思路是一样的，但是我的就比较冗余，把简化后的问题又复杂化了。所以还是贴在一块，供大家比对学习。（仅去空格代码）

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

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

卡哥文字以及视频讲解链接

重点

• 没有特别，就是第一眼可能懵。
• 右旋转，左旋转方法都一样，分清左右就好

c++实现

#include <iostream>
#include <string>
#include<algorithm>

int main(){
int k = 0;
std::string s;
std::cin >> k;
std::cin >> s;
if(k > s.size()){
return 1;
}
//右旋转
reverse(s.begin(),s.end());
reverse(s.begin(),s.begin() + k);
reverse(s.begin() + k,s.end());
std::cout << s << std::endl;

return 0;
}

28.实现strStr()

卡哥文字以及视频讲解链接

重点

• KMP
• 先去看KMP的具体实现。前缀表是什么？如何用代码实现？
• 前后缀比对的时候，都是从左往右一依次比对（有时候就是这里卡着没理解）。

c++实现

class Solution {
public:
void getNext(int* next, const string& s) {
int j = –1;
next[0] = j;
for(int i = 1; i < s.size(); i++) { // 注意i从1开始
while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
j = next[j]; // 向前回退
}
if (s[i] == s[j + 1]) { // 找到相同的前后缀
j++;
}
next[i] = j; // 将j（前缀的长度）赋给next[i]
}
}
int strStr(string haystack, string needle) {
if (needle.size() == 0) {
return 0;
}
vector<int> next(needle.size());
getNext(&next[0], needle);
int j = –1; // // 因为next数组里记录的起始位置为-1
for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始
while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
j = next[j]; // j 寻找之前匹配的位置
}
if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
j++; // i的增加在for循环里
}
if (j == (needle.size() – 1) ) { // 文本串s里出现了模式串t
return (i – needle.size() + 1);
}
}
return –1;
}
};

459.重复的子字符串

卡哥文字以及视频讲解链接

重点

• 具体实现看讲解，很详细
• KMP实现也可行，实现起来就更复杂了

c++实现

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

坚持就是胜利

• 第一天，搞定！
• 第二天，搞定！
• 第三天，搞定！
• 第四天，搞定！
• 第五天，搞定！
• 第六天，搞定！
• 第七天，搞定！
• 第八天，搞定！
• 第九天，KMP差点搞定，思路理清，代码还不能完全写出。

author