URL化

URL化。编写一种方法，将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。（注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）

示例 1：

输入："Mr John Smith ", 13
输出：“Mr%20John%20Smith”
示例 2：

输入：" “, 5
输出：”%20%20%20%20%20"

提示：

字符串长度在 [0, 500000] 范围内。

题解1

新建一个字符串，遍历原来的，直接按要求添加即可
需要额外的空间，并且时间都集中在添加上

class Solution {
public:string replaceSpaces(string S, int length) {string s;for(int i=0;i<length;i++){if(S[i]==' ')s+="%20";else s+=S[i];} return s;}
};

题解2：

先计算有多少个空格
注意：假定该字符串尾部有足够的空间存放新增字符
这意味着可能有多余空格（测试点20）
然后调整空间，成为合适的空间大小
最后双指针算法，线性时间下改变

class Solution {
public:string replaceSpaces(string S, int length) {int kong = 0;for(int i=0;i<length;i++)if(S[i]==' ')kong ++;int j = length + 2 * kong -1;S.resize(j+1);for(int i=length-1;i>=0;i--,j--){if(S[i]==' '){S[j]='0';S[j-1]='2';S[j-2]='%';j-=2;}else S[j]=S[i];}return S;}
};

题解3：

对题解2的优化，直接按照一样的方法往后放，最后取字串即可

class Solution {
public:string replaceSpaces(string S, int length) {int j = S.size()-1;for(int i=length-1;i>=0;i--,j--){if(S[i]==' '){S[j]='0';S[j-1]='2';S[j-2]='%';j-=2;}else S[j]=S[i];}return S.substr(j+1,string::npos);}
};

当然还有一个纯$O(N^2)$的算法写法，就是找到空格就把后面的字符往后放，然后再添加。