代码随想录算法训练营
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;
}