题目：请实现一个函数，把字符串中的每个空格替换成“%20”。例如，输入“We are happy.”，则输出“We%20are%20happy.”。
背景：网络编程中，如果URL参数中含有特殊字符如空格等，则可能导致服务器无法获得正确的参数值。需要将其转换成服务器可以识别的字符。
思路1.从头到尾扫描字符串，遇到空格就替换成“%20”，然后把之后的字符串向后移动两个字节。每替换一次就要将后面的字符串移动一次，时间复杂度为O(n2)。
思路2.从后面向前替换，这样每个字符只需要移动一次。准备两个指针，一个指向原始字符串的末尾，另一个指向替换后字符串的末尾（也就是原始字符串长度+空格数量*2的位置）。
代码如下：
void ReplaceBlank(char string[],int length)
{
if (string == nullptr || length < 0)
{
return;
}
int originalLength = 0; //originalLength 字符串实际长度
int numberOfBlank = 0;
int i = 0;
while (string[i] != '\0')
{
++originalLength;
if (string[i] == ' ' )
{
++numberOfBlank;
}
++i;
}
int newLength = originalLength + numberOfBlank * 2; //替换空格后的长度
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;
}
}
后续补充，直接开辟一个新的字符串数组。
时间复杂度为O(n)，空间复杂度为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;
}
};
