请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
注意下，字符用单引号' '括起来，字符串用双引号“ ”起来，那么“%20”就是一个字符串 里面有三个字符，而替换的空格只有一个字符。
所以替换大概是这样，找到第一个空格，字符串扩容两格，把第一个空格后面的字符统统向后移动两位，让后从第一个空格开始，替换符号’%‘，’2‘ ，’ 0 ‘。
之后就是找第二个空格，找第三个空格。
简单思路就是这样。
第一种解法 ，就是直接按照思路来，遇见空格，字符串扩容，空格后的字符后移两个位，从空格开始的三个位置填上要替换的字符 最坏时间复杂度O（N^2）,最坏空间复杂度O(N) 所以呢不太好。
class Solution { public: string replaceSpace(string s) { int length=s.size(); for(int i=0;i<length;i++) { if(s[i]==' ') { length+=2; s.resize(length); for(int j=length-1;j>i+2;j--) { s[j]=s[j-2]; } s[i]='%';s[i+1]='2';s[i+2]='0'; } } return s; } };
改进思路：直接遍历整个字符串，统计空格的数量然后直接扩容，之后从字符串末尾向前遍历，假设这个下标为i，再用一个指针指向没扩容前的字符串结尾,假设这个下标为j，不停的替换新字符串里的字符。
好吧，具体呢？？ 毕竟双指针不熟悉的话思路确实有点凌乱，所以不妨动动手画个图理解下。
首先想个问题，扩容之后的字符串和原来的字符串是同一个吗？？ 对，肯定是同一个，只是说的时候说新旧，但在实际的C++代码中，就是同一个字符串，因为C++的字符串是可以支持原地扩展的。
好，之后又有一个问题，新的字符串怎么填充？？
第一点：resize()函数扩展了字符串的大小，至于扩展后里面填了什么，不用去管，反正之后都要自己填。
第二点：i是扩容后的字符串从后向前遍历用的下标，那么s[i]应该填充什么？应该是s[j]，旧字符串的最后一位。
但是我们的要求是替换字符串的空格。假如s[j]是空格怎么办?
s[j]是空格那不就代表我们的s[i]要替换成“%20”吗，对不对？可是s[i]只能进去一个字符，所以替换的应该是s[ i ] ，s[ i-1 ]，s[ i-2 ]，这样就对了。
我们的被替换成了“%20”，i也应该变成i-2；
接下来呢？继续遍历， j--,i--;
好的，假如这时候s[ j ]位置已经不是空格了，我们又要做什么？ 直接替换s[ i ]=s[ j ];
之后j--;i--;
总之，只有这两种情况，以上也就是循环内要判断的东西。
那么什么时候循环结束？？ 最直观的，j变为0，表示旧的字符串遍历完了。
但这样不好，假如第一个空格前面有一千个字符，你把他们都遍历一遍，这不是浪费时间吗？所以，当j=i(也可以说j>=i)的时候,循环就已经可以结束了。
这就是整个替换流程。也是leedcode的标准解法。
时间复杂度O(N),空间复杂度O（1）；
class Solution { public: string replaceSpace(string s) { int count=0; int j=s.size()-1; for(int i=0;i<s.size();i++) { if(s[i]==' ') count++; } s.resize(s.size()+2*count); int i=s.size()-1; while(i>j) { if(s[j]==' ') { s[i]='0'; s[i-1]='2'; s[i-2]='%'; i-=2; } else { s[i]=s[j]; } i--,j--; } return s; } };