題目描述

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，將一個(gè)字符串中的空格替換成“%20”。例如，當(dāng)字符串為We Are Happy。則經(jīng)過替換之后的字符串為We%20Are%20Happy。

通過判斷空格的個(gè)數(shù)來確定轉(zhuǎn)換后的字符串長(zhǎng)度后，我們一般會(huì)想到由前往后替換空格，但是如此之來，后面的字符需要多次移動(dòng)，導(dǎo)致效率低下。反過來，如果由后往前進(jìn)行替換，那么需要改變位置的字符只需要移動(dòng)一次，時(shí)間復(fù)雜度為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測(cè)試版：

#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 << "請(qǐng)輸入字符串：" << endl;
    cin.getline(str, 1024);
    int length = 0, i = 0;
    while (str[length] != '\0')
        length++; 
    Solution s;
    s.replaceSpace(str, length);
    cout << "替換空格后的結(jié)果：" << endl;;
    while (str[i] != '\0') {
        cout << str[i];
        i++; 
    }
    return 0;
}