代码随想录第8天 | ● 344.反转字符串 ● 541. 反转字符串II ● 卡码网：54.替换数字

bamboo2233 / 2024-07-06 / 原文

题目：344.反转字符串

思路：

c++库函数 reverse
首尾交换双指针 swap

坑：

首尾交换，用的s[i]=s [n-i]; 报错数组访问出错，只有一个指针i，不能同时指向两个地方

补充：

库函数reverse
主要用来反转数组和字符串的函数

反转数组就是reverse（数组名，数组名+你想让他反转的数组长度）
反转字符串是reverse（s.begin(),s.end()）;

题目：541.反转字符串Ⅱ

思路：

根据字符串的长度，除以2k的结果和余数，使用双指针反转+swap
官方题解，reverse() + min ()
~~引用某位题友的话：可不可以别这样解题，你这样显得我很蠢。。。~~
~~烦躁了，每种题解都比我写的要简洁，吗喽噘嘴.gif~~
时间复杂度: O(n)
空间复杂度: O(1)

坑：

使用min（s.size（）,i+k）时，报错，类型不同，因为s.size()返回的是无符号类型。

class Solution {
public:
    string reverseStr(string s, int k) {
        int n=s.size();
        for(int i=0;i<n;i+=2*k){ 
            reverse(s.begin()+i,s.begin()+min(n,i+k));   
            //最后一组，i+k有没有超过s的长度，超了，访问数组越界，反剩余部分
            //没超，还是反转i到i+k部分，所以使用min比较s.size（）和i+k;
        }
        return s;
    }
};

补充：

左闭右开
一般编程的库函数都是左闭右开
max和min
函数定义在头文件中
std::max: 返回两个或更多参数中的最大值。
std::min: 返回两个或更多参数中的最小值
字符串长度
c++中使用s.length()和s.size() 获取长度，二者区别不大，返回的都是无符号类型。

题目：卡码网：54.替换数字

思路：

使用额外的空间，新数组，遍历添加，遇到数字添加number，
题解：原数组扩容，后序添加

很多数组填充类的问题，其做法都是先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
两个好处：
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;       
    }
}

补充：

字符串扩充
str.resize(k,c); //c可省
s.resize(s.size() + count * 5);
k:指定的字符数，若原字符串长度>k，则，原字符串删减到只有k个
若原字符串长度<k，则，原字符串扩大到k个
c:如果 k 大于字符串的长度，则 c 是要添加到新空格中的新字符。这是可选参数。