代码随想录算法训练营
Day8 代码随想录算法训练营第8 天 | LeetCode344.反转字符串 LeetCode 541. 反转字符串II 卡码网：54.替换数字
目录
前言
LeetCode344.反转字符串
LeetCode541. 反转字符串II
卡码网：54.替换数字
一、、LeetCode344.反转字符串
1.题目链接
2.思路
（1）双指针分别从第一个元素和最后一个元素出发（认为左闭右闭）
（2）不断交换两个指针所指的字符
3.题解
class Solution {
public:
void reverseString(vector<char>& s) {
int i = 0;
int j = s.size() - 1;
while (i < j) {
swap(s[i], s[j]);
i++;
j--;
}
}
};
二、LeetCode 541. 反转字符串II
1.题目链接
2.思路
（1）reverse可以自己实现，也可以使用库函数
如果自己实现reverse，并且以字符串指针为参数，一定要注意解引用时要写(*s)，因为解引用的优先级不够高
（使用引用作为参数可以避免这个问题）
（2）整个字符串中中包含round个2k周期，最后余下left个元素
1）讨论能凑出2k周期的情况：每个2k周期中反转前k个
2）再讨论left个元素：
left大于k，则将前k个反转
left小于k，则left全部反转
3.题解
class Solution {
public:
void reverse(string* s, int l, int r) {
int i = l;
int j = r;
while (i < j) {
swap((*s)[i], (*s)[j]);
i++;
j--;
}
}
string reverseStr(string s, int k) {
int n = s.size();
int round = n / (2 * k);
int left = n % (2 * k);
for (int i = 0; i < round; i++) {
reverse(&s, i * 2 * k, (i * 2 + 1) * k - 1);
}
if (left < k)
reverse(&s, n - left, n - 1);
else
reverse(&s, n - left, n - left + k - 1);
return s;
}
};
三、卡码网：54.替换数字
1.题目链接
2.思路
双指针法
（1）先求出字符串中有count个数字，需要增加5*count位
（2）双指针
指针i从后向前遍历原字符串
指针new_i从后向前遍历新的字符串
如果i遍历到字符：用new_i在新字符串中添加，并将new_i移动1位
如果i遍历到数字：用new_i在新字符串中按照r-e-b-m-u-n顺序添加，并将new_i移动6位
（3）这种方法没有创建新的字符串，但是可以确保原来的字符串会在被处理并加入答案后再覆盖掉
3.题解
（1）暴力法
#include<bits/stdc++.h>
#include<string>
using namespace std;
int main()
{
string s;
cin>>s;
std::vector<string> ans ;
int n=s.size();
for(int i=0;i<n;i++)
{
if(s[i]>='0'&&s[i]<='9')ans.push_back("number");
else
{
string temp;
temp.append(1,s[i]);
ans.push_back(temp);
}
}
string res;
int m=ans.size();
for(int i=0;i<m;i++ )
{
res+=ans[i];
}
cout<<res;
return 0;
}
（2）双指针法
#include<bits/stdc++.h>
#include<string>
using namespace std;
int main()
{
string s;
cin>>s;
std::vector<string> ans ;
int n=s.size();
int count=0;
for(int i=0;i<n;i++)
{
if(s[i]>='0'&&s[i]<='9')count++;
}
int m=n+count*5;
s.resize(m);
int new_i=m-1;
for(int i=n-1;i>=0;i--)
{
if(s[i]>='0'&&s[i]<='9')
{
s[new_i]='r';
s[new_i-1]='e';
s[new_i-2]='b';
s[new_i-3]='m';
s[new_i-4]='u';
s[new_i-5]='n';
new_i-=6;
}else
{
s[new_i]=s[i];
new_i--;
}
}
cout<<s;
return 0;
}
