一、問題

請實(shí)現(xiàn)一個(gè)函數(shù)，把字符串 s 中的每個(gè)空格替換成"%20"。

示例

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

二、解法

解法一

思路：調(diào)庫

既然使用了JDK的庫函數(shù)，最好還是去看一下源碼怎么實(shí)現(xiàn)的。如下，可以看到其實(shí)JDK內(nèi)部使用了正則表達(dá)式來替換全部的空格。正則雖然通用，但是在時(shí)間效率這一塊必然沒那么好，如果面試遇到這種問題，世界調(diào)庫也不太好。

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

• 直接調(diào)用jdk自帶的replace方法

具體實(shí)現(xiàn)：java

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

解法二

思路：使用額外空間

字符串在本質(zhì)上就是一個(gè)字符數(shù)組，那么可以直接新建一個(gè)字符數(shù)組，遍歷原有字符串的字符數(shù)組，如果遇到空格就新增三個(gè)字符%20。

當(dāng)然使用StringBuilder也可以。

• 首先創(chuàng)建一個(gè)字符數(shù)組，是原字符串長度的三倍（防止數(shù)組長度不夠）
• 遍歷字符串，如果不是空格直接塞
• 如果是空格，塞三個(gè)字符%20
• 時(shí)間復(fù)雜度O(n) 空間復(fù)雜度O(n)

具體實(shí)現(xià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);
    }

解法三

思路：通用數(shù)組插入問題

這種思路是要求空間復(fù)雜度為O(1),但是在java中字符串是不可變的，所以我們只能將字符串換成一個(gè)足夠長的字符數(shù)組。這個(gè)字符數(shù)組[0-length-1]是原本的字符串，后面全是\u0000。

顯然，因?yàn)榭崭袷且粋€(gè)字符，%20是三個(gè)字符。如果需要原地變更這個(gè)字符數(shù)組，就需要解決怎么插入字符的問題。因?yàn)閿?shù)組的插入時(shí)間復(fù)雜度是O(N),每一個(gè)空格都變更的話，整體時(shí)間復(fù)雜度會(huì)變成O(n*n)，這顯然是不能接受的。這邊介紹一個(gè)從后向前遍歷的方法，如果遇到數(shù)組的插入和刪除可以優(yōu)先考慮這種方法。

• 首先遍歷字符串計(jì)算空格的個(gè)數(shù)count
• 然后計(jì)算變更后字符數(shù)組的長度，length+2*count
• 雙指針，一個(gè)指針指向新數(shù)組長度-1，另一個(gè)指針指向length-1
• 從后向前遍歷，如果遇到空格就向前塞三個(gè)字符，其他的都塞原本的字符。
• 時(shí)間復(fù)雜度O(n) 空間復(fù)雜度O(1)

說明：下面的空間復(fù)雜度是O(n)，因?yàn)槲覜]有用輸入字符數(shù)組的方式，我直接字符串轉(zhuǎn)了一下。主要是思想

具體實(shí)現(xiàn)：java

public String replaceSpace(String s) {
        if (null == s) {
            return null;
        }
        //將字符復(fù)制到數(shù)組同時(shí)統(tǒng)計(jì)字符 ‘ ’的個(gè)數(shù)
        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 ++;
            }
        }
        //計(jì)算新數(shù)組的長度
        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);
    }

相關(guān)問題

有兩個(gè)排序的數(shù)組A1和A2，內(nèi)存在A的末尾有足夠多的空域空間容納A2。請實(shí)現(xiàn)一個(gè)函數(shù)，把A2中的數(shù)字插入A1中，并且所有的數(shù)字都是有序的。要求：

空間復(fù)雜度為O(1)。

解法

思路：通用數(shù)組的插入和刪除

具體實(shí)現(xiàn)：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)));
    }