思路
方法一：暴力解法(从头扫描)
从头到位开始扫描字符串，找到空格便用%20替换，这样做的缺陷是每次替换空格都需要移动空格后面所有的字符串，导致复杂度为O(n^2)
Paste_Image.png
方法一：从尾部扫描(O(n))
首先需要计算新字符串的长度为2*空格+原始长度，需要两个指针old和new 起始分别指向原始字符串和新字符串的尾部，从后往前扫描，每次old和new都往前走一步，并把old指向的字符赋值给new,如果old碰到空格，则在new前面依次插入"%,2,0"这三个字符，直到old=new为止。
Paste_Image.png
public String replaceSpace(String str){
char[] ch=str.toCharArray();
int spaceCount=0;
for(int i=0;i<ch.length;i++){
if(ch[i]==' ')
spaceCount++;
}
char[] ch1=new char[spaceCount*2+str.length()];
int newIndex=ch1.length-1;
int len=ch.length-1;
for(int i=len;i>=0;i--){
if(ch[i]==' '){
ch1[newIndex--]='0';
ch1[newIndex--]='2';
ch1[newIndex--]='%';
}else{
ch1[newIndex--]=ch[i];
}
}
return String.valueOf(ch1);
}
