总结
反转问题要活用双指针法，有效减少额外空间的使用
344.反转字符串
● 541. 反转字符串II
● 卡码网：54.替换数字
● 151.翻转字符串里的单词
● 卡码网：55.右旋转字符串
344.反转字符串
/*344. 反转字符串
简单
提示
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。*/
class Solution_344 {
public:
void reverseString(vector<char>& s) {
int left = 0;
int right = s.size() - 1;
while (left < right){
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left += 1;
right -=1;
}
}
};
● 541. 反转字符串II
/*541. 反转字符串 II
简单
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。*/
#include <algorithm>
class Solution_541 {
public:
/*
* 循环步长改为2k就可以
*/
string reverseStr(string s, int k) {
for (int i = 0; i < s.size(); i += (2 * k)) {
if (i + k <= s.size()) {
reverse(s.begin() + i, s.begin() + i + k);
} else {
reverse(s.begin() + i, s.end());
}
}
return s;
}
};
● 卡码网：54.替换数字
/*54. 替换数字（第八期模拟笔试）
时间限制：1.000S 空间限制：128MB
题目描述
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。
例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。
输入描述
输入一个字符串 s,s 仅包含小写字母和数字字符。
输出描述
打印一个新的字符串，其中每个数字字符都被替换为了number
输入示例
a1b2c3
输出示例
anumberbnumbercnumber
提示信息
数据范围：
1 <= s.length < 10000。*/
/*
* 数组填充类的问题可以通过扩充数组，并从后向前填充的方法解决，好处
* 1.不用额外申请空间
* 2.避免从前向后填充需要移动太多元素
*/
class Solution_kama_54 {
public:
string replaceNumber(string s) {
string res;
for (auto i : s) {
if (i >= 'a' && i <= 'z')
res.append(1, i);
else {
res.append("number");
}
}
return res;
}
string replaceNumber_double_pionts(string s) {
int num_count = 0;
for (auto i : s) {
if (i < 'a' || i > 'z')
num_count += 1;
}
s.resize(s.size() + (5 * num_count));
int left = s.size() - 1 - (5 * num_count);
int right = s.size() - 1;
while (left >= 0){
if(isalpha(s[left])){
s[right] = s[left];
right -= 1;
left -= 1;
} else{
s[right--] = 'r';
s[right--] = 'e';
s[right--] = 'b';
s[right--] = 'm';
s[right--] = 'u';
s[right--] = 'n';
left -= 1;
}
}
return s;
}
};
● 151.翻转字符串里的单词
/*
151. 反转字符串中的单词
中等
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例 1：
输入：s = "the sky is blue"
输出："blue is sky the"
示例 2：
输入：s = " hello world "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。
示例 3：
输入：s = "a good example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
提示：
1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词
进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。
*/
#include <algorithm>
class Solution_151 {
public:
string reverseWords(string s) {
//去除多余空格
int fast = 0;
int slow = 0;
#if 0
//去除前导空格
while (s.size() > 0 && s[fast] == ' ' && fast < s.size()) {
fast += 1;
}
//去除两个单词间有多余的空格
for (; fast < s.size(); ++fast) {
if (s[fast] == ' ' && fast + 1 < s.size() && s[fast] == s[fast + 1]) {
continue;
} else {
s[slow] = s[fast];
slow += 1;
}
}
if (s[slow - 1] == ' '){//去除尾随空格
s.resize(slow - 1);
} else
s.resize(slow);
#else
//优化方法,去除所有空格，加上单词间的空格
while (fast < s.size()){
if(s[fast] != ' '){
if(slow > 0)//第一个单词前不加
s[slow++] = ' ';//加上单词间的空格
while (fast < s.size() && s[fast] != ' '){//
s[slow++] = s[fast++];
}
} else
fast += 1;
}
s.resize(slow);
#endif
//整体反转
fast = 0;
slow = s.size() - 1;
while (fast < slow){
swap(s[fast], s[slow]);//也可创建临时变量或者位运算实现
fast += 1;
slow -= 1;
}
//反转单词
int count = 0;
for(int i = 0; i < s.size(); ++i){
if(s[i] == ' '){
reverse(s.begin() + i - count, s.begin() + i);//整体反转的局部使用
count = 0;
} else
count += 1;
}
reverse(s.end() - count, s.end());//反转最后一个单词
return s;
}
};
● 卡码网：55.右旋转字符串
/*55. 右旋字符串（第八期模拟笔试）
*
时间限制：1.000S 空间限制：128MB
题目描述
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。
给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。
例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。
输入描述
输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。
输出描述
输出共一行，为进行了右旋转操作后的字符串。
输入示例
2
abcdefg
输出示例
fgabcde
提示信息
数据范围：
1 <= k < 10000,
1 <= s.length < 10000;*/
class Solution_kama_55 {
public:
string stringRightReplace(string s, int k) {
int left = 0;
int right = s.size() - 1;
while (left < right){
swap(s[left++], s[right--]);
}
left = 0;
right = k - 1;
while (left < right){
swap(s[left++], s[right--]);
}
left = k;
right = s.size() - 1;
while (left < right){
swap(s[left++], s[right--]);
}
return s;
}
};
