剑指offer，面试题04，替换空格

àì夳堔傛蜴生んèń 2022-03-22 07:18 207阅读 0赞

题目：请实现一个函数，把字符串中的每个空格替换成"%20"，例如“We are happy.”，则输出“We%20are%20happy.”

最原始的思路是直接对字符串进行顺序扫描，然后再找到空格的地方，进行替换并移动之后的字符，但是这样的话时间复杂度就是O（n2）。

书上提供的一种思路是，先计算需要替换的有多少处，这样就能得到新建的char数组的大小了，然后，在老的char数组和新的char数组，都从后向前扫描，没有空格的地方直接复制到新的char数组中，有空格的地方，新的char数组，填入需要替换的字符串，这样一直扫描到两个数组的开头。这样就只进行了一次循环，时间复杂度是O（n）。

我在代码中使用replace方法实现了。

不过后来自己想了，因为在计算有多少处需要替换的时候，本身就是一次扫描，那么我可以记录下不需要替换和需要替换的字符串，然后将它加入一个String型的ArrayList的，利用Arraylist是顺序的和可以扩展的来实现这个目的，在程序中使用的是newRepalce这个方法，测试中用的是"%21"来替换空格。

下面是实现的代码：

package partOne;
    
    import java.util.ArrayList;
    
    public class ReplaceString {
        private String replace(String oldString , String replaceString){
            char[] oldCharArray = oldString.toCharArray();
            char[] replaceCharArray = replaceString.toCharArray();
    
            int length = oldCharArray.length;
            int count = 0;
    
            //计算需要替换的空位数目
            for(int i=0;i<length;i++){
                if(oldCharArray[i]==' '){
                    count++;
                }
            }
    
            //新数组长度
            int newLength = length+(3-1)*count;
    
            char[] newCharArray = new char[newLength];
    
            int oldPos = length-1;
            int newPos = newLength-1;
            //两个标识都从最后面开始向前面移动，直到到达最前方
            while(oldPos>=0&&newPos>=0){
                if(oldCharArray[oldPos]!=' ') //非空格的地方直接复制
                {
                    newCharArray[newPos] = oldCharArray[oldPos];
                    newPos--;
                    oldPos--;
                }
                else{ //空格的地方采用替代方式复制
                    newCharArray[newPos] = '0';
                    newCharArray[newPos-1] = '2';
                    newCharArray[newPos-2] ='%';
                    newPos = newPos-3;
                    oldPos--;
                }
            }
    
            String newString = String.valueOf(newCharArray);
            System.out.println("new String is:"+newString);
            return newString;
        }
    
        private String newReplace(String oldString,String ReplaceString){
            //创建存储各部分的ArrayList
            ArrayList<String> saveArrayList = new ArrayList<>();
            char[] oldCharArray = oldString.toCharArray();
            int length = oldCharArray.length;
            String tempString = "";
    
            //将原String分开存储入ArrayList
            for(int i=0;i<length;i++){
                if(oldCharArray[i]!=' '){
                    tempString = tempString+String.valueOf(oldCharArray[i]);
                    if(i==length-1){
                        saveArrayList.add(tempString);
                    }
                }
                if(oldCharArray[i]==' '){
                    if(tempString!=""){
                        saveArrayList.add(tempString);
                        tempString="";
                    }
                    saveArrayList.add(ReplaceString);
                }
            }
    
            String newString ="";
            for(String stringValue:saveArrayList){
                newString=newString+stringValue;
            }
            System.out.println("new String is:"+newString);
            return newString;
    
    
        }
    
        public static void main(String[] args) {
            String testString = "WE ARE HAPPY";
            String newString = new ReplaceString().replace(testString,"%20");
    
            new ReplaceString().newReplace(testString,"%21");
    
    
        }
    }

测试结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhcnJ5cHR0ZXI_size_16_color_FFFFFF_t_70][]

代码github地址：[代码地址][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhcnJ5cHR0ZXI_size_16_color_FFFFFF_t_70]: /images/20220322/47c781e198204736867a7ef353b73f65.png
[Link 1]: https://github.com/harrypitter/Offer.git