### 題目:實現一個函數,把字符串中的每個空格替換成 "%20"。(原字符串有足夠的空間容納替換后的字符串)
### 思路:因為要將一個字符替換成三個字符,因此如果從前往后遍歷原字符串的話,則每遇到一個空格就需要將該空格后面的字符串往后移動兩個位置。移動一次數組的時間復雜度為 O(n),所以總的時間復雜度為O(n<sup>2</sup>)。因此換種思路:從后往前遍歷。我們先遍歷一次原字符串,所花時間為 O(n),設置兩個指針,一個指向原字符串尾部('\0'),另一個指向替換之后的字符串的末尾,保持使第一個指針永遠指向第一個沒有被復制的字符,第二個指針指向將要被復制的字符或要被替換的字符存儲的最后一個位置,這樣當兩個指針重疊時,則表示空格已被替換完。因此最多也只遍歷了一遍原字符串,所以時間復雜度為 O(n)。總的時間復雜度也為 O(n)。
```
void replaceBlank(char str[])
{
if (str == nullptr || strlen(str) <= 0)
return;
int originalLen = 0, blankCnt = 0;
while (str[originalLen] != '\0') [
if (str[originalLen] == ' ') [
++blankCnt;
}
++originalLen;
}
int newLength = originalLen + blankCnt * 2;
int indexOfOriginal = originalLen;
int indexOfNew = newLength;
while (indexOfOriginal >=0 && indexOfOriginal < indexOfNew) {
if (str[indexOfOriginal] == ' ') {
str[indexOfNew--] = '0';
str[indexOfNew--] = '2';
str[indexOfNew--] = '%';
} else {
str[indexOfNew--] = str[indexOfOriginal];
}
--indexOfOriginal
}
}
```