題目描述

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，將一個(gè)字符串中的每個(gè)空格替換成“%20”。例如，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy

解題思路一

首先想到的就是新建一個(gè)數(shù)組，將原字符串的每個(gè)字符依此替換下來，碰到空格，則替換%20，一遍循環(huán)即可完成，時(shí)間復(fù)雜度o(n)，空間復(fù)雜度o(n)

思考：題目中使用的是StringBuffer，對(duì)比StringBuilder和StringBuffer，我們應(yīng)該使用哪個(gè)？

1、StringBuffer和StringBuilder都繼承于AbstractStringBuilder
2、看源碼可以發(fā)現(xiàn)，StringBuffer的實(shí)現(xiàn)方法都使用了synchronized關(guān)鍵字進(jìn)行加鎖同步，因此StringBuffer是線程安全的
3、在速度上，線程非安全要比線程安全快得多，由于此處單線程即可實(shí)現(xiàn)，推薦使用StringBuilder

代碼一

public String replaceSpace(StringBuffer str) {
        if (str == null) {
            return null;
        }
        StringBuilder replaceStr = new StringBuilder();
        // 從首位開始依此append
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ' ') {
                replaceStr.append('%');
                replaceStr.append('2');
                replaceStr.append('0');
            } else {
                replaceStr.append(str.charAt(i));
            }
        }
        return replaceStr.toString();
    }

解題思路二

如果考慮優(yōu)化，就需要考慮在o(1)的空間復(fù)雜度上，直接對(duì)原字符串進(jìn)行修改，在o(n)的時(shí)間復(fù)雜度上進(jìn)行操作

思考：在原字符串上進(jìn)行循環(huán)修改操作，應(yīng)該從前往后還是從后往前？

基于StringBuffer本質(zhì)是一個(gè)數(shù)組，我們可以想到：

1、從前往后操作，每次替換空格字符，都需要把空格往后的字符統(tǒng)一往后移，以此類推，需要在o(n^2)的時(shí)間復(fù)雜度才能完成

2、從后往前操作，在原字符的基礎(chǔ)上新增長(zhǎng)度，從原字符長(zhǎng)度最后一位開始，依此將字符復(fù)制在新長(zhǎng)度的最后一位，依此類推，兩次o(n)循環(huán)即可完成

代碼二

public String replaceSpace(StringBuffer str) {
        if (str == null) {
            return null;
        }
        int length = str.length();
        int newLength = length;
        // 計(jì)算新長(zhǎng)度
        for(int i =0 ;i<length;i++) {
            if(str.charAt(i) == ' ') {
                newLength+=2;
            }
        }
        str.setLength(newLength);
        // 從最后一位開始進(jìn)行復(fù)制
        for(int i = newLength - 1, j = length - 1; j>=0; j--) {
            if(str.charAt(j)!=' ') {
                str.setCharAt(i--, str.charAt(j));
            } else {
                str.setCharAt(i--, '0');
                str.setCharAt(i--, '2');
                str.setCharAt(i--, '%');
            }
        }
        return str.toString();
    }