题目：

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

时间复杂度为O(n)的解法

将目标字符串从末尾开始替换，首先准备两个指针，P1和P2。 P1指向原始字符串的末尾，而P2指向替换之后的字符串的末尾

image.png

public class Solution1 {
    public static void main(String[] args) {

        String s = "we are happy";
        System.out.println(replaceSpace(s));
    }

    public static String replaceSpace(String inputStr) {
        if (inputStr == null || inputStr.length() == 0) {
            return inputStr;
        }
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < inputStr.length(); i++) {
            if (inputStr.charAt(i) == ' ') {
                sb.append("%20");
            } else {
                sb.append(inputStr.charAt(i));
            }
        }
        return sb.toString();
    }
}

public class Solution2 {
    public static void main(String[] args) {

        String s = "we are happy";
        System.out.println(replaceSpace(s));


    }

    public static String replaceSpace(String inputStr) {
        if (inputStr == null || inputStr.length() == 0) {
            return inputStr;
        }
        int length = inputStr.length();
        char[] oldArray = inputStr.toCharArray();
        //假设字符数组足够大
        char[] newArray = new char[100];
        //统计空格数
        int count = 0;
        for (int i = 0; i < length; i++) {
            newArray[i] = oldArray[i];
            if (oldArray[i] == ' ') {
                count++;
            }
        }

        if (count == 0) {
            return inputStr;
        }

        int newLength = length + 2 * count;
        int head = length - 1;
        int tail = newLength - 1;
        while (head < tail) {
            if (newArray[head] == ' ') {
                newArray[tail] = '0';
                newArray[--tail] = '2';
                newArray[--tail] = '%';

            } else {
                newArray[tail] = newArray[head];
            }

            head--;
            tail--;
        }
        return new String(newArray);

    }
}