代码随想录 字符串 test 3

54. 替换数字（第八期模拟笔试）

        为了不使用额外的空间，采用双指针，通过用旧指针遍历原数组计算出数字个数，进而计算出新数组应有的大小，然后新指针指向新数组的最后，此时新，旧指针都位于两数组的末尾，同时从后往前遍历，遇到数组，新指针就需要写入number，遇到字母，就赋值旧数组的值。最终两个指针会同时指向数组起点。在整个过程中，旧指针先移动到旧指针末尾，然后两个指针一起移动到数组起点，时间复杂度为o(2n+kn)。

        为什么采用从后往前写入，因为不采用额外空间，为避免覆盖原数组信息而采用。即从后往前写入不会出现新写入的字符覆盖掉原数组还未遍历到的字符(因为新数组大小已经开辟好了)

        如果采用从前往后遍历，为了不采用额外空间(若采用时间复杂度与从后往前无异)，每次遍历到数字都要将它后面的字符移动到5个位置后，时间复杂度为o(n^2)

#include <iostream>
using namespace std;

int main(void){
    string s;
    int count = 0;
    int newpos, oldpos;//设置新单词指针，原单词指针
    
    cin >> s;
    
    for(int i = 0; i < s.size(); i++){
        if(s[i] <= '9' && s[i] >= '0')
            count++;
    }
    
    oldpos = s.size() - 1;
    s.resize(s.size() + count * 5);//更改新数组大小，每个数字要换成number，也就是增加5个
    newpos = s.size() - 1;
    
    while(oldpos >= 0){
        if(s[oldpos] <= '9' && s[oldpos] >= '0'){
            s[newpos--] = 'r';
            s[newpos--] = 'e';
            s[newpos--] = 'b';
            s[newpos--] = 'm';
            s[newpos--] = 'u';
            s[newpos--] = 'n';
        }else{
            s[newpos--] = s[oldpos];
        }
        oldpos--;
    }
    
    cout << s;
    
    return 0;
}