前言
一组比较基础的字符串类型题目
344. 反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须 原地 修改输入数组 、使用 O(1) 的额外空间解决这一问题。
思路
- reverse函数的内部实现
reverse(s.begin(),s.end());
拓展知识
字符串类 string s1; 和容器类 vector<char> s2; 的区别：
string用于表示可变长度的字符 序列。拥有丰富的字符串操作方法，适用于文本处理、字符串拼接、字符串查找等场景vector<char>用于表示可变长度的字符 数组。仅能使用数组操作方法，但可以使用指针，适用于二进制数据处理、数组操作等场景
代码实现
class Solution {
public:
void reverseString(vector<char>& s) {
int i=0;
int j=s.size()-1;
char temp;
while(i<j){
temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
};
整理格式后：
class Solution {
public:
void reverseString(vector<char>& s) {
for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
swap(s[i],s[j]);
}
}
};
541. 反转字符串 II
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
- 如果剩余字符少于
k个，则将剩余字符全部反转。 - 如果剩余字符小于
2k但大于或等于k个，则反转前k个字符，其余字符保持原样。
思路
看起来条件很多，但其实可以合并：
- 剩余字符在
>2k和<2k处理上没有区别，都是翻转前k个。因为有i<s.size()，即使<2k时+(2*k)也不会溢出 - 只在
>=k和<k的处理上产生分支，一个翻转前k，一个翻转剩余所有
因此最终在for循环中只需要设置 >=k 和 <k 两个条件判断
代码实现
class Solution {
public:
string reverseStr(string s, int k) {
for(int i=0; i<s.size(); i+=(2*k)){
// 1. 每计数 2k 个字符就翻转前 k 个
// 2. 剩余字符大于等于 k 个，同样翻转前 k 个
if(s.size()-i >= k){
reverse(s.begin()+i, s.begin()+i+k);
}
// 3. 剩余字符小于 k 个，则全部翻转
else{
reverse(s.begin()+i, s.end());
}
}
return s;
}
};
54. 替换数字
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。
例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。
难点
- 如何不借助额外辅助空间？
思路
-
对于定长的字符串，可以通过统计数字个数以预留空间，实现原地拓展
- 关键函数：
s.resize(s.size() + count*5);
- 关键函数：
-
从头遍历的双指针法，每次查找到数字，都要将后续所有字符向后移动5位，效率极低。因此可以尝试从尾部遍历，预留空间必定会在未来被填满，因此直接移动至尾部，实现一次移动至最终位置。
代码实现
#include <iostream>
using namespace std;
int main(){
string s;
while(cin>>s){
int left = s.size()-1;
int count = 0;
for(int i=0; i<s.size(); i++){
if(s[i]>'0' && s[i]<'9'){
count++;
}
}
// 6个字符，除了数字自己的空间，还要额外扩展5个
s.resize(s.size() + count*5);
int right = s.size()-1;
while(left >= 0){
if(s[left]>'0' && s[left]<'9'){
s[right--] = 'r';
s[right--] = 'e';
s[right--] = 'b';
s[right--] = 'm';
s[right--] = 'u';
s[right--] = 'n';
}
else{
s[right--] = s[left];
}
left--;
}
cout<< s << endl;
}
}
