剑指Offer04-空格替换

题目：

/**
     * 请实现一个函数，把字符串中的每个空格替换成"%20"。
     * 例如输入"We are happy"，则输出"We%20are%20happy"
     */

解题思路：

若不考虑时间复杂度的情况，从前向后遍历，在原始的数组上进行操作，每当遇到空格，就将替换的字符插入，后面的字符向后移动，这样若存在o(n)个空格的话，

长度为o(n)的字符就会向后面进行o(n)次移动复制，时间复杂度为o(n^2)；

若考虑时间复杂度，就需要减少频繁复制的次数，解决的办法可以是在创建一个新的数组来保存替换后的字符串。

代码如下：

import java.util.Scanner;

public class StringBlank {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        
        System.out.println(replace(s));
    }
    
    private static String replace(String s) {
        char[] c = s.toCharArray();
        int count = 0;
        for(int i=0;i<c.length;i++) {
            if(c[i] == ' ') {
                //计算出空格的个数，从而得出新数组的长度
                count++;
            }
        }
        
        //创建一个新数组，来保存新的字符串
        char[] temp = new char[c.length+2*count];
        //下标i指向新数组的末尾
        int i = c.length+2*count-1;
        //下标j指向旧数组的末尾
        int j = c.length-1;
        
        while(i>=0) {
            if(c[j] == ' ') {
                temp[i] = '0';
                temp[i-1] = '2';
                temp[i-2] = '%';
                i=i-3;
            }else {
                temp[i] = c[j];
                i--;
            }
            j--;
        }
        return new String(temp);
    }
}