C++算法训练营 Day8 字符串（1）

1.反转字符串

• LeetCode：344.反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用O(1)的额外空间解决这一问题。

示例 1：

输入：s = [“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]

示例 2：

输入：s = [“H”,“a”,“n”,“n”,“a”,“h”]
输出：[“h”,“a”,“n”,“n”,“a”,“H”]

• 解题思路：

反转字符串与反转链表本质上有着很多共同的思路，但是字符串本身是一种数组，元素的存储是连续的，因此我们可以使用双指针的方法来实现字符串的反转。具体实现方法为：指针i从数组头部开始，指针j从数组尾部开始。每次交换i和j指向的元素，然后i向后移动，j向前移动。

循环条件：i < s.size()/2，即只需要遍历到数组的一半即可完成反转。因为当i到达中间位置时，j也到达中间位置（从尾部算起），此时已经完成所有交换操作。例如:

1.字符串长度为5（奇数）时，循环条件为i < 2，即i取0,1，交换索引(0,4)和(1,3)，索引2（中间位置）不需要交换。

2.字符串长度为6（偶数）时，循环条件为i < 3，交换索引(0,5)、(1,4)、(2,3)。

class Solution {
public:void reverseString(vector<char>& s) {for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {swap(s[i],s[j]);}}
};

当然，循环条件中我们也可以写为：while(i < j)，这种写法同样有效，而且可能更易读。循环条件是i < j，当两个指针相遇或交叉时停止。同样地：

1.对于偶数长度，指针会在中间相遇后停止（例如，长度为4时，交换索引0-3和1-2，然后i=2, j=1，此时i>j，停止）。
2.对于奇数长度，指针会在中间元素相遇（例如，长度为5，交换0-4和1-3，然后i=2, j=2，此时i=j，不再满足i<j，停止）。

void reverseString(vector<char>& s) {int left = 0, right = s.size() - 1;while (left < right) {swap(s[left++], s[right--]);}
}

如果题目关键的部分直接用库函数就可以解决，建议不要使用库函数。，如果库函数仅仅是解题过程中的一小部分，并且已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数。

如本题中，swap()中的实现原理为：

char temp = s[i];
s[i] = s[j];
s[j] = temp;

所以，我们在解这道题时，没有使用reverse库函数，而使用swap库函数。

2.反转字符串II

• LeetCode：541.反转字符串II

给定一个字符串s和一个整数k，从字符串开头算起，每计数至2k个字符，就反转这2k字符中的前k个字符。

如果剩余字符少于k个，则将剩余字符全部反转。
如果剩余字符小于2k但大于或等于k个，则反转前k个字符，其余字符保持原样。

示例 1：

输入：s = “abcdefg”, k = 2
输出：“bacdfeg”

示例 2：

输入：s = “abcd”, k = 2
输出：“bacd”

• 解题思路：

本题给出了反转的限制条件，因此在循环中需要对其进行界定。首先循环条件为i += (2 * k)，即i每次前进2k个字符，这是因为我们在2k个字符中，只对前k个字符进行反转，因此i指针处理完一段后立刻跳转到下一段的起始位置。

for (int i = 0; i < s.size(); i += (2 * k))

题目中对反转的区间给了界定：
（1）如果剩余字符小于2k但大于或等于k个，则反转前k个字符，其余字符保持原样。
对于情况1，给出边界条件：i + k <= s.size()，其中i为当前处理的起始位置（索引），k为需要反转的字符数量，s.size()为字符串总长度，那么剩余字符数即为从位置 i 到字符串末尾的字符数量 = s.size() - i，即s.size() - i ≥ k。这里大家不要理解错了，这个边界条件是从第一段就开始生效，先判断第一段的字符数是否大于等于k，此时i = 0，如果k = 2，对于字符串abcdefg来说，第一段肯定是够得，第二段也是满足的。

if (i + k <= s.size()) {// 反转从 i 开始的 k 个字符// reverse 使用左闭右开区间 [i, i+k)reverse(s.begin() + i, s.begin() + i + k);} 

那么这段代码的运行流程应该是：

原始字符串：a b c d e f g，要求k= 2
处理步骤：

1. i=0：剩余字符为 7 - 0 = 7 >= 2 → 反转[0,2) → [a,b] → b a c d e f g
2. i=4：剩余字符7 - 4 = 3 >= 2 → 反转[4,6) → [e,f] → b a c d f e g
3. i=8：超出长度 → 结束 最终结果：b a c d f e g → “bacdfeg”

（2）如果剩余字符少于k个，则将剩余字符全部反转。

else {// 反转剩余所有字符reverse(s.begin() + i, s.end());}

原始字符串：a b c d e f g h，要求k = 3
处理步骤：

1. i=0：剩余字符8>=3 → 反转[0,3) → [a,b,c] → c b a d e f g h
2. i=6：剩余字符2<3 → 反转[6, end) → [g,h] → c b a d e f h g
   最终结果：c b a d e f h g → “cbadefhg”

完整代码如下：

class Solution {
public:string reverseStr(string s, int k) {// 每次前进 2k 个字符for (int i = 0; i < s.size(); i += (2 * k)) {// 情况1：剩余字符 >= k 个if (i + k <= s.size()) {// 反转从 i 开始的 k 个字符// reverse 使用左闭右开区间 [i, i+k)reverse(s.begin() + i, s.begin() + i + k);} // 情况2：剩余字符 < k 个else {// 反转剩余所有字符reverse(s.begin() + i, s.end());}}return s;}
};

3.替换数字

• 卡码网：替换数字

给定一个字符串s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串"a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。
输入描述

输入一个字符串 s,s 仅包含小写字母和数字字符。

输出描述

打印一个新的字符串，其中每个数字字符都被替换为了number

输入示例

a1b2c3

输出示例

anumberbnumbercnumber

• 解题思路：

#include <iostream>
using namespace std;int main() {string s;while (cin >> s) {int sOldIndex = s.size() - 1; //原字符串的最后一个字符位置int count = 0; //统计数字的个数//第一遍遍历：统计字符串中数字的数量for (int i = 0; i < s.size(); i++) {if (s[i] >= '0' && s[i] <= '9') {count++;}}//扩充字符串大小：每个数字替换为"number"(6个字符)//原数字占1个位置，需要额外增加5个位置s.resize(s.size() + count * 5);int sNewIndex = s.size() - 1; //新字符串的最后一个位置// 从后向前处理字符串while (sOldIndex >= 0) {if (s[sOldIndex] >= '0' && s[sOldIndex] <= '9') {//替换数字为"number"（逆序写入）s[sNewIndex--] = 'r'; //number的最后一个字符s[sNewIndex--] = 'e'; s[sNewIndex--] = 'b';s[sNewIndex--] = 'm';s[sNewIndex--] = 'u';s[sNewIndex--] = 'n'; //number的第一个字符} else {//非数字字符直接复制s[sNewIndex--] = s[sOldIndex];}sOldIndex--; //处理前一个字符}cout << s << endl; }
}