剑指Offer -- 替换空格（C++）

题目描述

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy。则经过替换之后的字符串为We%20Are%20Happy。

通过判断空格的个数来确定转换后的字符串长度后，我们一般会想到由前往后替换空格，但是如此之来，后面的字符需要多次移动，导致效率低下。反过来，如果由后往前进行替换，那么需要改变位置的字符只需要移动一次，时间复杂度为O(n)。

class Solution {
public:
    void replaceSpace(char *str, int length) {
        int blank = 0;
        for (int i = 0; i < length; i++) {
            if (str[i] == ' ') 
                blank++;
        }
        int newLength = length + blank * 2;
        for (int i = length - 1; i >= 0; i--) {
            if (str[i] == ' ') {
                str[--newLength] = '0';
                str[--newLength] = '2';
                str[--newLength] = '%';
            } else {
                str[--newLength] = str[i];
            }
        }
    }
};

附上本地的IDE测试版：

#include <iostream>
using namespace std;
 
class Solution {
public:
    void replaceSpace(char *str, int length) {
        int blank = 0;
        for (int i = 0; i < length; i++) {
            if (str[i] == ' ') 
                blank++;
        }
        int newLength = length + blank * 2;
        for (int i = length - 1; i >= 0; i--) {
            if (str[i] == ' ') {
                str[--newLength] = '0';
                str[--newLength] = '2';
                str[--newLength] = '%';
            } else {
                str[--newLength] = str[i];
            }
        }
    }
};

int main() {
    // 前提是字符串的空间足够大 
    // char str[1024] = "We Are Happy";
    char *str = new char[1024];
    cout << "请输入字符串：" << endl;
    cin.getline(str, 1024);
    int length = 0, i = 0;
    while (str[length] != '\0')
        length++; 
    Solution s;
    s.replaceSpace(str, length);
    cout << "替换空格后的结果：" << endl;;
    while (str[i] != '\0') {
        cout << str[i];
        i++; 
    }
    return 0;
}