代码随想录算法训练营Day08|344. 反转字符串、541. 反转字符串 II、剑指 Offer 05. 替换空格、151. 反转字符串中的单词、剑指 Offer 58 - II. 左旋转字符串
344. 反转字符串
题干强调要原地修改输入数组，不能使用额外的字符数组进行赋值。这里采用双指针法，两指针分别从首尾位置进行元素互换,空间复杂度为O(1)。并且不需要考虑字符长度奇/偶的情况，因为中间元素不需要变动。
字符串也是一种数组，所以元素在内存中是连续分布，这就决定了反转链表和反转字符串方式上还是有所差异的。
代码如下：
class Solution {
public:
void reverseString(vector<char>& s) {
int len = s.size();
int i = 0, j = len - 1;
while (i < j) {
char temp = s[i];
s[i++] = s[j];
s[j--] = temp;
}
}
};
其实直接使用库函数就可以实现：
reverse(s.begin(), s.end());
541. 反转字符串 II
本题在字符串反转的基础上，对字符串进行一定规则的部分反转，关键在于对遍历过程的模拟，我们逐个取2k个字符并翻转前k个字符。每次对起点遍历的间隔设置为2k即可。另外注意库函数reverse在反转部分字符串内容时的使用方式：
// 用于反转整个字符串
reverse(s.begin(), s.end());
// 用于反转部分字符串，假设反转下标范围是[i, i+k-1]（合计k个字符）
reverse(s.begin() + i, s.begin() + i + k);
注意reverse的使用区间是左闭右开的。另外本题字符串末尾组可能不满k个，在确定反转下标前需要对末尾位数进行判断，注意只需要判断需要反转的前k位即可，代码如下：
class Solution {
public:
string reverseStr(string s, int k) {
for (int i = 0; i < s.size(); i += (2 * k)) {
// 仅需要判断反转的前k位即可
if (i + k < s.size())
reverse(s.begin() + i, s.begin() + k + i);
else
reverse(s.begin() + i, s.end());
}
return s;
}
};
剑指 Offer 05. 替换空格
①新字符串拼接
如果考虑直接在给定字符串中插入空格的替换符，会对顺序存储结构的数组造成极大开销，因此考虑重新拼接一个新的字符串。
class Solution {
public:
string replaceSpace(string s) {
string res;
for (int i = 0; i < s.size(); i++) {
if (s[i] == ' ')
res += "%20";
else
res += s[i];
}
return res;
}
};
这样会造成一定空间的额外开销。
②原地拓充数组+双指针法
其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。为了不额外造成存储开销，考虑统计空格个数后原地进行数组拓展，会用到如下函数：
s.resize(new_size);
将数组拓充后，我们使用双指针来重新赋值：
- 前指针指向原数组末位元素：用来将原数组的元素移动到新数组的正确位置
- 后指针指向拓展数组的末位元素：实际赋值修改新数组的位置
当前指针匹配上空格时，则在后指针按要求插入替换字符即可。关键是需要倒序遍历，避免了从前先后填充元素导致每次添加元素都要将添加元素之后的所有元素向后移动。最后当前后指针重合，说明前面没有空格导致缩进了，即修改完成，代码如下：
class Solution {
public:
string replaceSpace(string s) {
int count = 0, len = s.size();
// 先根据空格个数进行字符串拓充
for (int i = 0; i < s.size(); i++) {
if (s[i] == ' ')
count++;
}
// 注意数组拓展为替换字符的差值
s.resize(s.size() + 2 * count);
// 从末尾开始使用双指针对空格进行替换
int cur = s.size() - 1;
int ori = len - 1;
while (cur != ori) {
if (s[ori] != ' ')
s[cur--] = s[ori--];
else {
s[cur--] = '0';
s[cur--] = '2';
s[cur--] = '%';
ori--;
}
}
return s;
}
};
151. 反转字符串中的单词
class Solution {
public:
void removeExtraSpaces(string& s) {
int slowIndex = 0, fastIndex = 0; // 定义快指针，慢指针
// 去掉字符串前面的空格
while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {
fastIndex++;
}
for (; fastIndex < s.size(); fastIndex++) {
// 去掉字符串中间部分的冗余空格
if (fastIndex - 1 > 0
&& s[fastIndex - 1] == s[fastIndex]
&& s[fastIndex] == ' ') {
continue;
} else {
s[slowIndex++] = s[fastIndex];
}
}
if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格
s.resize(slowIndex - 1);
} else {
s.resize(slowIndex); // 重新设置字符串大小
}
}
string reverseWords(string s) {
// 先去除首部空格
removeExtraSpaces(s);
int wordLeft = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == ' ') {
reverse(s.begin() + wordLeft, s.begin() + i);
// 开始搜索下一个左边界
while (s[i + 1] == ' ')
i++;
wordLeft = i + 1;
}
}
reverse(s.begin() + wordLeft, s.end());
reverse(s.begin(), s.end());
return s;
}
};
剑指 Offer 58 - II. 左旋转字符串
class Solution {
public:
string reverseLeftWords(string s, int n) {
reverse(s.begin(), s.begin() + n);
reverse(s.begin() + n, s.end());
reverse(s.begin(), s.end());
return s;
}
};