题目描述
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路
思路一：暴力替换，遇到空格后，将后面字符往后挪2位，最坏时间复杂度$O(n^2)$
思路二：创建一个新字符串，根据str从前往后对新字符每位赋值，如果遇到空格，新字符串加入%20，否则加入$str[i]$。时间复杂度$O(n)$，空间复杂度$O(n)$。
思路三：先扫一遍串$str$，查看$str$中有多少个空格。假设有$cnt$个空格，则说明$str$长度需要加长$2*cnt$位。因此我们可以从后往前遍历$str$，同时维护一个递减指针$id=length+2*id$，遍历$str$的同时对$str[id]$赋值，赋值规则类同思路二。时间复杂度$O(n)$，空间复杂度$O(1)$。
Code
class Solution {
public:
void replaceSpace(char *str,int length) {
int cnt=0;
for(int i=0;i<length;++i)if(str[i]==' ')cnt++;
int id=length+cnt*2;
str[id--]=0;
for(int i=length-1;i>=0;--i){
if(str[i]==' '){
str[id--]='0';
str[id--]='2';
str[id--]='%';
}
else str[id--]=str[i];
}
}
};