替换空格

   请实现一个函数，把字符串中每个空格替换成“20%”，例如：输入“we are happy.”，则输出“we20%are20%happy.”。

如果我们最直观的做法从头到尾扫描字符串，每一次碰到空格的时候做替换。假设字符串长度是n，对每个空格字符，需要移动后面的O（n）个字符，因此对含有O（n）个空格字符的字符串而言总的时间效率是O（n^2）。在这里如果用java的替换方法replace可以轻松搞定

时间复杂度O（n^2）的代码

package com.feimao.com.feimao.a2.test;

public class ReplaceBlank {
    static final String s = "We are happy.";
    public static void main(String[] args){
        System.out.println("原数组 = " + s);
        System.out.println("替换的数组 " + s.toString().replace(" " , "20%"));
    }
}

  我们换一种思路，把从前向后替换改成从后向前替换。

  我们可以先遍历一次字符串，这样就能统计出字符串的空格的总数。变可以由此计算替换之后字符串的总长度。每替换一个空格，长度增加2，因此替换后的字符串的长度等于原来长度加上2*空格数。

统计字符串的空格总数代码

    public static int getBlankNum(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            String tempS = String.valueOf(s.charAt(i));
            if (tempS.equals(" ")) {
                count++;
            }
        }
        return count;
    }

  首先准备两个指针，p1和p2。p1指向原始字符串的末尾，p2指向替换之后字符串的末尾。接下来我们向前移动指针p1，逐个把它指向字符复制到p2指向的位置，直到碰到第一个空格为止，也就是做了字符串拷贝。整个算法代码如下：

package com.feimao.com.feimao.a2.test;

public class ReplaceBlank {
    public static String s = "We are happy.";
    public static int getBlankNum(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            String tempS = String.valueOf(s.charAt(i));
            if (tempS.equals(" ")) {
                count++;
            }
        }
        return count;
    }

    public static void printArray(char[] testArray) {
        for (char i : testArray) {
            System.out.print(i);
        }
        System.out.println();
    }

    public static void replaceBlank(String s) {
        if (s == null || s.length() < 0) {
            System.out.println("请正确输入数组");
            return;
        }
        int length = s.length();
        int newLength = s.length() + getBlankNum(s) * 2;
        char[] temparray = new char[newLength];
        System.arraycopy(s.toCharArray(), 0, temparray, 0, s.toCharArray().length);
        int p1 = length - 1;
        int p2 = newLength - 1;
        while (p1 >= 0 && p1 != p2) {
            if (temparray[p1] == ' ') {
                temparray[p2] = '0';
                p2--;
                temparray[p2] = '2';
                p2--;
                temparray[p2] = '%';
                p2--;
            } else {
                temparray[p2] = temparray[p1];
                p2--;
            }
            p1--;
        }
        System.out.println("替换空格后的字符串: ");
        printArray(temparray);
    }

    public static void main(String[] args) {
        System.out.println("原字符串 = " + s);
        replaceBlank(s);
    }


}

运行结果：