代码随想录算法训练营第六天 -- 字符串1 || 344.反转字符串I / 541.反转字符串II / kamacoder54.替换数字--第八期模拟笔试

344.反转字符串I

文档讲解：代码随想录算法训练营
视频讲解：算法视频公开课
状态：做出来了，用了一个临时字符，反复交换就行了

思路

本道题是实现reverse()函数，所以不要直接使用reverse()函数。
本道题是要使用双指针，使用相向双指针的方法。

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

这里swap()交换函数的实现如下：

        	// swap()函数实现方法一
            tmp = s[i];
            s[i] = s[j];
            s[j] = tmp;

        	// swap()函数实现方法二
            s[i] ^= s[j];
            s[j] ^= s[i];
            s[i] ^= s[j];

541.反转字符串II

文档讲解：代码随想录算法训练营
视频讲解：算法视频公开课
状态：没做出来，没读懂题，绕蒙了。

题目理解

这道题读题有点难理解。
这道题是在讲，一个字符串s，每2k个为一组。
每组中前k个元素反转，后k个不变。
如果剩下的字符数目不足2k个，那么还有两种情况：
（1）如果不足k个，那么这些元素反转
（2）如果k < 剩下字符数目 < 2k，那么前k个反转，剩下的不变。

解题思路

这道题我们for循环里，i += 2k进行循环，每次循环中，只反转[i, i + k)区间的字符，反转完结束本次循环。如果剩余字符不足k个，那么反转[i, n)区间的字符。
代码：

class Solution {
public:
    string reverseStr(string s, int k) {
        int n = s.size();

        // 进入循环，每 2k 个字符为一组
        for (int i = 0; i < n; i += 2 * k) {
            // 如果这组字符数 > k 个，那么前 k 个字符反抓
            if (i + k <= n) {
                reverse(s.begin() + i, s.begin() + i + k);
                continue;
            }

            // 如果不足 k 个元素，反转剩余元素
            reverse(s.begin() + i, s.begin() + n);
        }
        
        return s;
    }
};

边界细节

这里有几个边界问题的细节
1）if()的判断条件：i + k <= n。假设n = 3，k = 3，i = 0，第一次是符合的，如果没有等于，那么就不符合，明显不对。
2）reverse()传入的参数：这里是左闭右开区间，第 k 个元素的下表是 i + k - 1，那么反转的区间是[i, i + k - 1]。

reverse()函数的实现

class Solution {
public:
    void reverse(string& s, int start, int end) {
        for (int i = start, j = end - 1; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }
    string reverseStr(string s, int k) {
        int n = s.size();
        for (int i = 0; i < n; i += 2 * k) {
            if (i + k <= n) {
                reverse (s, i, i + k);
                continue;
            }
            reverse (s, i, n);
        }
        return s;
    }
};

kamacoder54.替换数字 – 第八期模拟笔试

文档讲解：代码随想录算法训练营
状态：看题解懂了

解题思路

第一步：
首先我们要给原来字符串扩容，这里用到的是resize()函数。遇到数字，就给原来字符串扩容5个空间

    int count = 0;
    for (int i = 0; i < s.size(); i ++) {
        if (s[i] >= '0' && s[i] <= '9') {
            count ++;
        }
    }

第二步：
我们设原来字符串的最后字符索引为n1 = s.size() - 1，扩容后新字符串的最后一个字符的索引为n2 = s.size() - 1。

    int n1 = s.size() - 1;
    s.resize(s.size() + 5 * count);
    int n2 = s.size() - 1;

第三步：
我们遍历原字符串，如果原字符串某个字符是字母，那么就在新字符串中最后一个位置填上原来字符串的字母；
如果原来字符串某个字符是数字，那么就在新字符串从后到前依此填上r, e, b, m ,u ,n

    while (n1 >= 0) {
        if (s[n1] >= '0' && s[n1] <= '9') {
            s[n2 --] = 'r';
            s[n2 --] = 'e';
            s[n2 --] = 'b';
            s[n2 --] = 'm';
            s[n2 --] = 'u';
            s[n2 --] = 'n';
        } else {
            s[n2 --] = s[n1];
        }
        n1 --;
    }

完整代码如下：

#include <iostream>
using namespace std;

int main() {
    string s;
    cin >> s;
    int count = 0;
    for (int i = 0; i < s.size(); i ++) {
        if (s[i] >= '0' && s[i] <= '9') {
            count ++;
        }
    }

    int index1 = s.size() - 1;
    s.resize(s.size() + 5 * count);
    int index2 = s.size() - 1;

    while (index1 >= 0) {
        if (s[index1] >= '0' && s[index1] <= '9') {
            s[index2 --] = 'r';
            s[index2 --] = 'e';
            s[index2 --] = 'b';
            s[index2 --] = 'm';
            s[index2 --] = 'u';
            s[index2 --] = 'n';
        } else {
            s[index2 --] = s[index1];
        }
        index1 --;
    }

    cout << s << endl;
}

注意：
（1）while()循环的条件是index1 >= 0，而不是index1 --，因为最后已经减了，index1的范围可以到0，它指的是索引下标。
（2）注意index1和index2的含义，不要弄混。