题解 | #替换空格#

//看到这题第一时间能想到一些思路。比如从前往后进行原地替换——这样每次替换后都要向后移动大量元素，时间复杂度是n^2（准确来说是n*k，取决于空格的数量）。
//另一个思路是开辟一个新字符串，每次遇到空格后都写入%20，其他时候则正常写入。这样做的缺点是要额外花On的空间。
//代码随想录提供了一个原地操作的On办法。先统计空格的数量，然后为字符串开辟额外的空间，用双指针法，一个指向新空间末，一个指向原字符串末。两个一起往左移动。没遇到空格时，将原字符串的内容拷到新空间中。遇到空格时，则让指向原字符串的指针暂停一下，让指向新空间的连动3步把%20打出来。
class Solution {
public:
    string replaceSpace(string s) {
        int spacecount=0;
        int originsize=s.size();//扩容前的size
        for (int i=0; i<originsize; i++) {
            if (s.at(i)==char{' '}) {
                spacecount++;
            }
        }
        //扩容
        s.resize(originsize+spacecount*2);
        int originindex=originsize-1;
        int newindex=s.size()-1;
        while (spacecount>0) {
            if(s.at(originindex)!=char{' '})//没有遇到空格就做正常的平移复制
            {
                s.at(newindex)=s.at(originindex);
                newindex--;
                originindex--;
            }else {
                s.at(newindex--)=char{'0'};
                s.at(newindex--)=char{'2'};
                s.at(newindex--)=char{'%'};
                originindex--;
                spacecount--;
            }
        }
        return s;
    }
};