5.替换空格

题目：请实现一个函数，把字符串中的每个空格替换成“%20”。例如，输入“We are happy.”，则输出“We%20are%20happy.”。

背景：网络编程中，如果URL参数中含有特殊字符如空格等，则可能导致服务器无法获得正确的参数值。需要将其转换成服务器可以识别的字符。

• 思路1.从头到尾扫描字符串，遇到空格就替换成“%20”，然后把之后的字符串向后移动两个字节。每替换一次就要将后面的字符串移动一次，时间复杂度为O(n²)。

• 思路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;
    }
};