目录
1--反转字符串
2--反转字符串II
3--反转字符串中的单词
4--KMP算法
5--重复的子字符串
1--反转字符串
主要思路:文章来源:https://www.toymoban.com/news/detail-690267.html
双指针算法,交换两个指针的字符;
#include <iostream>
#include <vector>
class Solution {
public:
void reverseString(std::vector<char>& s) {
if(s.size() == 0) return;
int l = 0, r = s.size() - 1;
while(l < r){
std::swap(s[l], s[r]);
l++;
r--;
}
}
};
int main(int argc, char* argv[]){
// s = ["h","e","l","l","o"]
std::vector<char> s = {'h', 'e', 'l', 'l', 'o'};
Solution S1;
S1.reverseString(s);
for(auto c : s) std::cout << c << " ";
std::cout << std::endl;
return 0;
}
2--反转字符串II
主要思路:
以 2k 个字符为一组进行遍历;
#include <iostream>
#include <string>
#include <algorithm>
class Solution {
public:
std::string reverseStr(std::string s, int k) {
for(int i = 0; i < s.length(); i += 2*k){
if(i + k <= s.length()) {
std::reverse(s.begin() + i, s.begin() + i + k);
}
else{
std::reverse(s.begin() + i, s.end());
}
}
return s;
}
};
int main(int argc, char* argv[]){
// s = "abcdefg", k = 2
std::string test = "abcdefg";
int k = 2;
Solution S1;
std::string res = S1.reverseStr(test, k);
std::cout << res << std::endl;
return 0;
}
3--反转字符串中的单词
主要思路1:
遍历提取每一个有效的单词,存储在一个栈中,最后遍历栈连接字符串即可;空间复杂度为O(N);
#include <iostream>
#include <stack>
#include <string>
class Solution {
public:
std::string reverseWords(std::string s) {
std::stack<std::string> stk;
std::string tmp = "";
for(int i = 0; i < s.length(); i++){
if(s[i] == ' ' && tmp == "") continue; // 单词前的空格
else if(s[i] == ' ' && tmp != ""){ // 单词间的空格
stk.push(tmp);
tmp = "";
}
else{
tmp += s[i];
}
}
stk.push(tmp); //最后一个有效单词
std::string res;
while(!stk.empty()){
if(res.length() == 0) res += stk.top();
else{
res += " ";
res += stk.top();
}
stk.pop();
}
return res;
}
};
int main (int argc, char *argv[]){
std::string test = "the sky is blue";
Solution S1;
std::string res = S1.reverseWords(test);
std::cout << res << std::endl;
return 0;
}
主要思路2:
不使用辅助空间,要求空间复杂度为O(1);首先使用快慢指针剔除多余的空格,接着反转所有字符,最后对单词的字符进行再次反转;
#include <iostream>
#include <string>
#include <algorithm>
class Solution {
public:
std::string reverseWords(std::string s) {
//去除多余的空格(参考移除数组的元素,使用快慢指针)
removeExtraSpace(s);
//反转所有字符
std::reverse(s.begin(), s.end());
//按单词再次反转
int start = 0;
for(int i = 0; i < s.length(); i++){
// 遇到单词间的空格
if(s[i] == ' ') {
std::reverse(s.begin()+start, s.begin()+i);
start = i + 1;
}
}
// 反转最后一个单词
std::reverse(s.begin()+start, s.end());
return s;
}
void removeExtraSpace(std::string &s){
int slow = 0;
for(int fast = 0; fast < s.length(); fast++){
if(s[fast] == ' ') continue;
if(slow != 0){ // 单词间的空格
s[slow] = ' ';
slow++;
}
while(fast < s.length() && s[fast] != ' '){ //将非空格字符覆盖到slow的位置
s[slow] = s[fast];
slow++;
fast++;
}
}
s.resize(slow);
}
};
int main (int argc, char *argv[]){
std::string test = "the sky is blue";
Solution S1;
std::string res = S1.reverseWords(test);
std::cout << res << std::endl;
return 0;
}
4--KMP算法
数据结构笔记--KMP算法的实现
5--重复的子字符串
主要思路:
文章来源地址https://www.toymoban.com/news/detail-690267.html
#include <iostream>
#include <string>
#include <algorithm>
class Solution {
public:
bool repeatedSubstringPattern(std::string s) {
std::string ss = s + s;
ss = ss.substr(1, ss.size() - 2);
if(ss.find(s) != -1) return true;
else return false;
}
};
int main(int argc, char* argv[]){
// s = "abab"
std::string test = "abab";
Solution S1;
bool res = S1.repeatedSubstringPattern(test);
if(res) std::cout << "true" << std::endl;
else std::cout << "false" << std::endl;
return 0;
}
到了这里,关于代码随想录笔记--字符串篇的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!