思路

方法一：暴力解法(从头扫描)

从头到位开始扫描字符串，找到空格便用%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);
}