題目描述

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

注意

原來(lái)一個(gè)空格字符，替換之后，變成‘%’，‘2’，‘0’三個(gè)字符，字符串長(zhǎng)度會(huì)變長(zhǎng)。如果是在原來(lái)的字符串上做替換，要保證原來(lái)的字符串有足夠的空余內(nèi)存。

從前向后，時(shí)間復(fù)雜度為O(n^2)

從頭到尾掃描字符串，每次碰到空格字符時(shí)做替換，空格后所有的字符向后移2個(gè)字節(jié)。

從后向前，時(shí)間復(fù)雜度O(n)

先遍歷一遍字符串，求出所有空格的總數(shù)和字符串實(shí)際長(zhǎng)度。計(jì)算出替換之后的字符串的總長(zhǎng)度，從字符串最后開(kāi)始復(fù)制和替換，包括‘\0’。

class Solution {
public:
    void replaceSpace(char *str, int length) {
        if (str == NULL || length <= 0)
            return;

        int blanksize = 0;  //空格數(shù)
        int len=0;          //數(shù)組實(shí)際長(zhǎng)度
        for (int i = 0; str[i]!='\0'; i++)//注意此處判斷條件不是i<length
        {
            len++;
            if (str[i] == ' ')
                blanksize++;
        }

        int newLen = len + blanksize * 2;
        if (newLen > length)
            return;
        int j = newLen;
        for (int i = len; i >= 0; i--)
        {
            if (str[i] != ' ')
                str[j--] = str[i];
            else
            {
                str[j--] = '0';
                str[j--] = '2';
                str[j--] = '%';
            }
        }
    }
};