一、问题

请实现一个函数，把字符串 s 中间的每个空格替换成"%20"。

示例

输入：s = "We are happy." 输出："We%20are%20happy."

二、解法解法一思路：调库

既然使用了JDK的库函数，最好还是去看一下源码怎么实现的。如下，可以看到其实JDK内部使用了正则表达式来替换全部的空格。正则虽然通用，但是在时间效率这一块必然没那么好，如果面试遇到这种问题，世界调库也不太好。

public String replaceAll(String regex, String replacement) {        return Pattern.compile(regex).matcher(this).replaceAll(replacement);    }

public String replaceSpace(String s) {        return s.replaceAll(" ","%20");    }

字符串在本质上就是一个字符数组，那么可以直接新建一个字符数组，遍历原有字符串的字符数组，如果遇到空格就新增三个字符%20。

当然使用StringBuilder也可以。

首先创建一个字符数组，是原字符串长度的三倍（防止数组长度不够）遍历字符串，如果不是空格直接塞如果是空格，塞三个字符%20时间复杂度O(n) 空间复杂度O(n)具体实现：java

public String replaceSpace(String s) {        if (null == s) {            return null;        }        char[] result = new char[s.length() * 3];        int size = 0;        for (int i = 0; i < s.length(); i++) {            if (' ' == s.charAt(i)) {                result[size++] = '%';                result[size++] = '2';                result[size++] = '0';            } else {                result[size++] = s.charAt(i);            }        }        return new String(result, 0, size);    }

这种思路是要求空间复杂度为O(1),但是在java中字符串是不可变的，所以我们只能将字符串换成一个足够长的字符数组。这个字符数组[0-length-1]是原本的字符串，后面全是\u0000。

显然，因为空格是一个字符，%20是三个字符。如果需要原地变更这个字符数组，就需要解决怎么插入字符的问题。因为数组的插入时间复杂度是O(N),每一个空格都变更的话，整体时间复杂度会变成O(n*n)，这显然是不能接受的。这边介绍一个从后向前遍历的方法，如果遇到数组的插入和删除可以优先考虑这种方法。

首先遍历字符串计算空格的个数count然后计算变更后字符数组的长度，length+2*count双指针，一个指针指向新数组长度-1，另一个指针指向length-1从后向前遍历，如果遇到空格就向前塞三个字符，其他的都塞原本的字符。时间复杂度O(n) 空间复杂度O(1)

**说明：**下面的空间复杂度是O(n)，因为我没有用输入字符数组的方式，我直接字符串转了一下。主要是思想

具体实现：java

public String replaceSpace(String s) {        if (null == s) {            return null;        }        //将字符复制到数组同时统计字符 ‘ ’的个数        int count = 0;        char[] result = new char[s.length() * 3];        for (int i = 0; i < s.length(); i++) {            result[i] = s.charAt(i);            if (result[i] == ' ') {                count ++;            }        }        //计算新数组的长度        int length = s.length() + (count << 1);        for (int i = length - 1, j = s.length() - 1; i >= 0 && j >= 0; j--) {            if (result[j] == ' ') {                result[i--] = '0';                result[i--] = '2';                result[i--] = '%';            } else {                result[i--] = result[j];            }        }        return new String(result,0, length);    }

有两个排序的数组A1和A2，内存在A的末尾有足够多的空域空间容纳A2。请实现一个函数，把A2中的数字插入A1中，并且所有的数字都是有序的。要求：

空间复杂度为O(1)。

解法思路：通用数组的插入和删除具体实现：java

public static int[] mergeSortArray(int[] a1, int a1Length, int[] a2){        if (null == a1 || a1Length == 0 || null == a2 || a2.length == 0) {            return a1;        }        int length = a1Length + a2.length;        int i = a1Length - 1;        int j = length - 1;        int k = a2.length - 1;        while (i >= 0 && j >= 0 && k >= 0) {            if (a1[i] >= a2[k]) {                a1[j--] = a1[i--];            } else {                a1[j--] = a2[k--];            }        }        if (k >= 0) {            for (int l = 0; l <= k; l++) {                a1[j--] = a2[k--];            }        }        return a1;    }    public static void main(String[] args) {        int[] a1 = {1,2,3,4,5,0,0,0,0,0,0,0,0,0,0,0,0};        int[] a2 = {4,5,7,9,11,13};        System.out.println(Arrays.toString(mergeSortArray(a1,5 ,a2)));    }