代码随想录算法训练营Day08 | 344.反转字符串、541. 反转字符串II、卡码网：54.替换数字

---

344.反转字符串

• 题目链接：344. 反转字符串 - 力扣（LeetCode）
• 讲解链接：代码随想录 (programmercarl.com)
• 状态：一遍AC。

思路与重点

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

s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];//原理如下：
a=(a ^ b);
b=(a ^ b) ^ b=a ^ (b ^ b) = a ^ 0 = a;
a=(a ^ b) ^ a =(a ^ a) ^ b = 0 ^ b =b;

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]);}}
};

541. 反转字符串II

• 题目链接：541. 反转字符串 II - 力扣（LeetCode）
• 讲解链接：代码随想录 (programmercarl.com)
• 状态：两次AC。

思路与重点

• 其实在遍历字符串的过程中，只要让** i += (2 * k)**，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。因为要找的也就是每2 * k 区间的起点，这样写，程序会高效很多。所以当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。

class Solution {
public:string reverseStr(string s, int k) {for (int i = 0; i < s.size(); i += (2 * k)) {// 1. 每隔 2k 个字符的前 k 个字符进行反转// 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符if (i + k <= s.size()) {reverse(s.begin() + i, s.begin() + i + k );} else {// 3. 剩余字符少于 k 个，则将剩余字符全部反转。reverse(s.begin() + i, s.end());}}return s;}
};

卡码网：54.替换数字

• 题目链接：54. 替换数字（第八期模拟笔试） (kamacoder.com)
• 讲解链接：代码随想录 (programmercarl.com)
• 状态：一遍AC。

思路与重点

• 其实很多数组填充类的问题，其做法都是先预先给数组扩容带填充后的大小，然后在从后向前进行操作。这么做有两个好处：1. 不用申请新数组。2. 从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

#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++;}}// 扩充字符串s的大小，也就是将每个数字替换成"number"之后的大小s.resize(s.size() + count * 5);int sNewIndex = s.size() - 1;// 从后往前将数字替换为"number"while (sOldIndex >= 0) {if (s[sOldIndex] >= '0' && s[sOldIndex] <= '9') {s[sNewIndex--] = 'r';s[sNewIndex--] = 'e';s[sNewIndex--] = 'b';s[sNewIndex--] = 'm';s[sNewIndex--] = 'u';s[sNewIndex--] = 'n';} else {s[sNewIndex--] = s[sOldIndex];}sOldIndex--;}cout << s << endl;       }
}