题目
请实现一个函数，把字符串中的每个空格替换成”%20”。
你可以假定输入字符串的长度最大是1000。
注意输出字符串的长度可能大于1000。
样例
输入：”We are happy.”
输出：”We%20are%20happy.”

解法一：复制到新str

简单粗暴
时间复杂度O(n)，空间复杂度O(n)

class Solution {
public:
    string replaceSpaces(string &str) {
        string ans;
        for (int i = 0; i < str.size(); i++) {
            if (str[i] == ' ')
                ans += "%20";
            else ans += str[i];
        }
        return ans;
    }
};

解法二：从后往前就地双指针

求出string最终长度，然后从后往前修改字符串，和从前往后的方式相比，避免了数组的移动
这在合并两个数组或者是字符串当中是一种比较通用的做法，可以有效避免移动
时间复杂度O(n)，空间复杂度O(1)

resize：改变容器的size，并将空间初始化，可以直接访问 reserve：改变容器的capacity，就是预分配的空间大小，没有被初始化，不可以直接访问

class Solution {
public:
    string replaceSpaces(string &str) {
        int len = 0;
        for (auto c: str) {
            if (c == ' ')
                len += 3;
            else len++;
        }
        int i = str.size() - 1, j = len - 1;
        str.resize(len);
        while (i >= 0) {
            if (str[i] == ' ') {
                str[j--] = '0';
                str[j--] = '2';
                str[j--] = '%';
            }
            else
                str[j--] = str[i];
            i--;
        }
        return str;
    }
};