題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)百姓，把字符串中的每個(gè)空格替換成“%20”渊额。例如，輸入“We are happy.”垒拢，則輸出“We%20are%20happy.”旬迹。
背景：網(wǎng)絡(luò)編程中，如果URL參數(shù)中含有特殊字符如空格等求类，則可能導(dǎo)致服務(wù)器無法獲得正確的參數(shù)值奔垦。需要將其轉(zhuǎn)換成服務(wù)器可以識(shí)別的字符。
思路1.從頭到尾掃描字符串尸疆，遇到空格就替換成“%20”椿猎，然后把之后的字符串向后移動(dòng)兩個(gè)字節(jié)。每替換一次就要將后面的字符串移動(dòng)一次仓技，時(shí)間復(fù)雜度為O(n2)鸵贬。
思路2.從后面向前替換，這樣每個(gè)字符只需要移動(dòng)一次脖捻。準(zhǔn)備兩個(gè)指針阔逼，一個(gè)指向原始字符串的末尾，另一個(gè)指向替換后字符串的末尾（也就是原始字符串長(zhǎng)度+空格數(shù)量*2的位置）地沮。
代碼如下：
void ReplaceBlank(char string[],int length)
{
if (string == nullptr || length < 0)
{
return;
}
int originalLength = 0; //originalLength 字符串實(shí)際長(zhǎng)度
int numberOfBlank = 0;
int i = 0;
while (string[i] != '\0')
{
++originalLength;
if (string[i] == ' ' )
{
++numberOfBlank;
}
++i;
}
int newLength = originalLength + numberOfBlank * 2; //替換空格后的長(zhǎng)度
if (newLength > length)
{
return;
}
int indexOfNew = newLength;
int indexOfOriginal = originalLength;
while (indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
{
if (string[indexOfOriginal] == ' ')
{
string[indexOfNew --] = '0';
string[indexOfNew --] = '2';
string[indexOfNew --] = '%';
}
else
{
string[indexOfNew --] = string[indexOfOriginal];
}
-- indexOfOriginal;
}
}
后續(xù)補(bǔ)充嗜浮，直接開辟一個(gè)新的字符串?dāng)?shù)組羡亩。
時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)危融。
方法：
class Solution {
public:
string replaceSpaces(string &str) {
string str1;
for (int i = 0;i < str.size();i++)
{
if (str[i] == ' ')
{
str1 += "%20";
}
else
{
str1 += str[i];
}
}
return str1;
}
};
