代码随想录--字符串--替换空格题型

①这道题可以直接申请一个临时数组，然后遍历字符串，是空格则加入20%，最后再把临时数组转化为字符串。
怎么把一个数组转化为字符串?
如数组arry[]，
string newstr = new string(arry,0,arry.size()-1);
return newstr;
而且临时数组的空间要申请大一些。
public String replaceSpace(String s) {
        int length = s.length();
        char[] array = new char[length * 3];
        int index = 0;
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                array[index++] = '%';
                array[index++] = '2';
                array[index++] = '0';
            } else {
                array[index++] = c;
            }
        }
        String newStr = new String(array, 0, index);
        return newStr;
    }

②或者用栈，只是出栈后结果是需要来个翻转吗？有点不大会。

③不过上面的这些方法都需要时间复杂度O(n)，并且空间复杂度O(n)。
接下来有个时间复杂度O(n)，但是空间复杂度O(1)的做法，要是学会了也不难，接下来说说这种解法。
这个解法就不需要申请新的空间。
第一步，首先扩充数组到每个空格替换成"%20"之后的大小。
比如这道题，每个空格要变成20%，即一个空格变成了3个空格，所以每个空格处要添加2个空格，即先统计字符串中有多少个空格，然后+多少个空格*2。怎么添加字符串长度?
//s.resize(n); resize将string类中有效字符改变到n个。
第二步，从后向前替换空格，也就是双指针法，过程如下：
i指向新长度的末尾，j指向旧长度的末尾。
然后i,j往前，如果s[j]不是空格则把s[j]赋给s[i]; 如果s[j]是空格，则s[i]赋为0, s[i-1]赋为2, s[i-2]赋为%，并且i往前移三格。然后继续i，j一起往前移继续如此轮下去。

④有同学问了，为什么要从后向前填充，从前向后填充不行么？
从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。

⑤其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
这么做有两个好处：
不用申请新数组。
从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

当i=j时，即说明扩充的空格都用完了，说明前面已经没有空格要变成20%了，所以就可以结束了，所以循环结束条件就是j<i，而不是j<=i。
 

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0; // 统计空格的个数
        int sOldSize = s.size();
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                count++;
            }
        }
        // 扩充字符串s的大小，也就是每个空格替换成"%20"之后的大小
        s.resize(s.size() + count * 2);
        int sNewSize = s.size();
        // 从后先前将空格替换为"%20"
        for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
            if (s[j] != ' ') {
                s[i] = s[j];
            } else {
                s[i] = '0';
                s[i - 1] = '2';
                s[i - 2] = '%';
                i -= 2;
            }
        }
        return s;
    }
};