劍指offer編程題Java實現——替換空格

 1 package Solution;
 2 
 3 /**
 4  * 劍指offer面試題4：替換空格
 5  * 題目：請事先一個函數，把字符串中的每個空格替換成"%20"。
 6  * 例如輸入"We are happy."，則輸出"We%20are%20happy."。
 7  * @author GL
 8  *
 9  */
10 public class No4ReplaceSpace {
11 
12     public static void main(String[] args) {
13         String string1="We are happy.";
14         String string2=" We  are happy. ";
15         String string3="Wearehappy.";
16         //String string4=null;
17         String string5="";
18         String string6=" ";
19         String string7="    ";
20         System.out.println(replaceSpace(string1.toCharArray()));
21         System.out.println(replaceSpace(string2.toCharArray()));
22         System.out.println(replaceSpace(string3.toCharArray()));
23         //System.out.println(replace(string4.toCharArray()));
24         System.out.println(replaceSpace(string5.toCharArray()));
25         System.out.println(replaceSpace(string6.toCharArray()));
26         System.out.println(replaceSpace(string7.toCharArray()));
27         System.out.println(replaceSpace(new StringBuffer(string1)));
28         System.out.println(replaceSpace(new StringBuffer(string2)));
29         System.out.println(replaceSpace(new StringBuffer(string3)));
30         //System.out.println(replaceSpace(new StringBuffer(string4)));
31         System.out.println(replaceSpace(new StringBuffer(string5)));
32         System.out.println(replaceSpace(new StringBuffer(string6)));
33         System.out.println(replaceSpace(new StringBuffer(string7)));
34     }
35     
36     /*
37      * 時間復雜度為O(n)的解法：利用數組從後向前替換
38      * 1、先遍歷一次字符串，統計出要替換的字符的個數
39      * 2、創建新的臨時數組，數組長度為初始字符串字符個數+替換每個字符多出來的字符個數*要替換的字符個數
40      * 3、從原來字符串數組後面開始向前進行復制、替換到臨時數組。兩個數組下標變量分別為原始字符數組長度-1，臨時數組長度-1
41      * 4、原始字符數組的字符如果不為空格，則把這個字符復制到臨時數組的對應位置，兩個數組下標都減1
42      * 5、原始字符數組的字符如果為空格，則把臨時數組相對應的位置從後向前依次寫入替換的字符，臨時數組下標減少相應的替換的字符數量
43      * 6、循環復制替換，直到初始數組的下標小於0，此時替換完畢，臨時數組轉換成字符串後返回
44      */
45     public static String replaceSpace(char[] string){
46         if(string==null)
47             return null;
48         int originalLength=string.length;
49         int spaceCount=0;
50         for(int i=0;i<originalLength;i++){
51             if(string[i]==' ')
52                 spaceCount++;
53         }
54         int newLength=originalLength+2*spaceCount;
55         char[] temp=new char[newLength];
56         int i=originalLength-1;
57         int j=newLength-1;
58         while(i>=0){
59             if(string[i]==' '){
60                 temp[j]='0';
61                 temp[j-1]='2';
62                 temp[j-2]='%';
63                 j=j-3;
64             }else{
65                 temp[j]=string[i];
66                 j=j-1;
67             }
68             i=i-1;
69         }
70         return new String(temp);
71     }
72     
73     /*
74      * 時間復雜度為O(n)，利用StringBuffer實現
75      * 通過indexOf(String str,int fromIndex)方法和subSequence(int start,int end)方法聯合實現
76      */
77     public static String replaceSpace(StringBuffer str){
78         if(str==null)
79             return null;
80         int fromIndex=0;
81         int index=0;
82         StringBuffer temp =new StringBuffer();
83         while(index<=str.length()){
84             index=str.indexOf(" ",fromIndex);
85             if(index>=0){
86                 temp.append(str.subSequence(fromIndex, index)).append("%20");
87                 index=index+1;
88                 fromIndex=index;
89             }else{
90                 temp.append(str.substring(fromIndex, str.length()));
91                 break;
92             } 
93         }
94         return temp.toString();
95     }
96 
97 }