剑指 Offer 05. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1：

输入：s = "We are happy."

输出："We%20are%20happy."

限制：

0 <= s 的长度 <= 10000

思路及代码

1.求出空格数

2.修改字符串s长度以容纳多出来的字符-->s.resize(s.size() + 2*空格数)

3.从后向前替换空格，也就是双指针法，过程如下：i指向新长度的末尾，j指向旧长度的末尾。

    3.1当 s[i] 不为空格时：执行 s[j] = s[i] ；

    3.2当 s[i] 为空格时：将字符串闭区间 [j-2, j] 的元素修改为 "%20" ；由于修改了 3 个元素，因此需要 j -= 2 ；

4. 返回s

一些问题：

为什么要从后向前填充，而不是从前向后填充？

从前往后每次都要移动添加位置后的元素，时间复杂度为O（n^2），而从后往前用双指针时，后面的指针在修改扩充的数组内容时，是不影响前面的指针遍历原数组的

Code:

class Solution {
public:
    string replaceSpace(string s) {
        int nums=0,len = s.size();
        //统计空格个数
        for(char c : s){
            if(c == ' ') nums++;
        }
        //扩充长度
        s.resize(s.length() + 2*nums);
        //倒序双指针修改
        for(int i = len-1,j=s.size()-1;i<j;i--,j--){
           if(s[i] != ' ') s[j] = s[i];
           else{
               s[j] = '0';
               s[--j] = '2';
               s[--j] = '%';
           }
        }
        return s;
        
    }
};