Junyuan's Homepage

344. 反转字符串

题目链接：click here
文章讲解：click here
题目描述：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

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

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
思路：
简单的双指针法，首尾对调，当左右指针相遇时不需要对调。

代码：

class Solution
{
public:
    void reverseString(vector<char> &s)
    {
        int n = s.size();
        if (n == 0 || n == 1)
        {
            return;
        }

        int left = 0;
        int right = n - 1;

        while (left < right)
        {
            swap(s[left++], s[right--]);
        }
    }
};

时空复杂度分析：
遍历一次vector ：O( $n$ ) 时间复杂度
无额外存储：O(1) 空间复杂度

541. 反转字符串II

题目链接：click here
文章讲解：click here
题目描述：给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。

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

如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
思路：
左指针k个k个前向遍历，循环改变一个控制是否反转的bool变量，
为true时就反转左右指针闭区间内的元素，直到超出n-1。
右指针 > n-1时，强行置右指针为 n-1.

代码：

class Solution
{
public:
    void reserve(string &s, int start, int end)
    {
        while (start < end)
        {
            swap(s[start++], s[end--]);
        }
    }

    string reverseStr(string s, int k)
    {
        int n = s.size();
        int left = 0;
        int right = left + k - 1;
        bool reverse = true;
        while (left < n)
        {
            if (right > n - 1)
            {
                right = n - 1;
            }
            if (reverse)
            {
                reserve(s, left, right);
                reverse = false;
            }
            else
            {
                reverse = true;
            }
            left = left + k;
            right = right + k;
        }

        return s;
    }
};

时空复杂度分析：
遍历string：O(n) 时间复杂度
无需额外存储：O(1) 空间复杂度

卡码网：54.替换数字

题目链接：click here
文章讲解：click here
题目描述：给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。

例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。

对于输入字符串 “a5b”，函数应该将其转换为 “anumberb”
我的思路：
简单，就是单起一个字符串，然后遍历原字符串，不是数字就照抄，是数字就在结果后面 + “number”。

代码：

#include <iostream>
using namespace std;
int main()
{
    string s;

    std::cin >> s;

    string res;

    for (char c : s)
    {
        if (c - 'a' >= 0 && c - 'a' <= 25)
        {
            res.push_back(c);
        }
        else
        {
            res += "number";
        }
    }

    std::cout << res << std::endl;
}

时间复杂度：O(n)，遍历字符串
空间复杂度：O(n)，额外用了一个字符串
讲解思路：
还可以进一步优化为无需额外存储的。

具体的，这里是替换字符为更长的字符串，那么需要扩充字符串长度（resize不会改变已有的内容，而是在后面加一些内存）。扩充的具体长度: “number” 长度 6 减去原有的单个字符长度 1 = 5，再乘以总数字个数 count。

从前往后填充是麻烦的，因为每次填充前都要先把后面的往后搬运。
扩充问题，是需要从后往前填充，就能避免冗余的搬运。

具体的流程由双指针来控制。当双指针对齐时，说明前方已经没有数字了，可以提前退出遍历。

讲解代码：

#include <iostream>
using namespace std;
int main() {
    string s;
    while (cin >> s) {
        int count = 0; // 统计数字的个数
        for (int i = 0; i < s.size(); i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                count++;
            }
        }
        int sOldIndex = s.size() - 1;
        // 扩充字符串s的大小，也就是将每个数字替换成"number"之后的大小
        s.resize(s.size() + count * 5);
        int sNewIndex = s.size() - 1;
        // 从后往前将数字替换为"number"
        //while (sOldIndex >= 0) { 这里可以换为 sOldIndex < sNewIndex
        while (sOldIndex < sNewIndex) {
            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;       
    }
}

时间复杂度：O(n)，遍历字符串
空间复杂度：O(1)，仅有临时存储

今日收获

个人博客更新。若Blog有误或是有其他想交流的，左侧有联系方式。
复习：
今日核心思想：字符串的操作：反转、替换；原地扩充与原地删减都可用双指针法，注意是从前往后填充还是从后往前填充，关键是要避免冗余的移动大块数据。

反转字符串：简单的双指针题，首尾对调即可。
反转字符串II：模拟题，在上一题的基础上去写，复用反转的接口，那么本题只需要额外定义好题设流程即可。
替换数字：扩充问题，是需要从后往前填充，就能避免冗余的搬运。和之前那道移除元素可以一起理解，它是删减问题，就直接从前往后填充就行了。这两道题都是用双指针来原地修改原数据，并避免冗余的移动大块数据。
耗时：2h

Junyuan Lu(陆俊元)

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

344. 反转字符串

541. 反转字符串II

卡码网：54.替换数字

今日收获