题目

请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

题目分析

从前往后遍历,每次遇到空格都需要将后面的后移。时间复杂度较高。

先扩容到对应的长度,也就是原来的长度+空格数*2.

从后往前遍历(用两个指针一个指向新数组,一个指向现遍历到哪个字符)

如果不为空格直接移到后面那个指针的位置。

如果为空格,将%20移到后面的位置(顺序是0 2 %)

代码

public String replaceSpace(StringBuffer str) {
        int len = str.length();
        if(len == 0) return str.toString();
        
        //记录空格数量,然后统计出空格数量
        int num = 0;
        for(int i = 0;i < len;i++){
            if(str.charAt(i) == ' '){
                num++;
            }
        }
        
        //新字符串的长度应该为num*2,也就是最后一个数下标为len + num * 2 - 1,oldInde用于记录当前遍历到哪儿
        int newIndex = len + num * 2 - 1;
        int oldIndex = len - 1;
        str.setLength(newIndex + 1);
        
        for(;oldIndex >= 0;oldIndex--){
            if(str.charAt(oldIndex) == ' '){
                str.setCharAt(newIndex--, '0');
                str.setCharAt(newIndex--, '2');
                str.setCharAt(newIndex--, '%');
            }else{
                str.setCharAt(newIndex--,str.charAt(oldIndex));
            }
        }
        return str.toString();
    }