替換空格

問題描述：

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

解題思路

API

• 時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(1)

class Solution {
    public String replaceSpace(String s) {
        if (s == null || s.length() == 0)
            return "";
        return s.replace(" ", "%20");
    }
}

StringBuilder

• 時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(n)

class Solution {
    public String replaceSpace(String s) {
        if (s == null || s.length() == 0)
            return "";
        StringBuilder sb = new StringBuilder();
        for (char c: s.toCharArray()) {
            if (c == ' ') sb.append("%20");
            else sb.append(c);
        }
        return sb.toString();
    }
}

劍指Offer思路

• 只是為了加深下這種思路的影響，首先統(tǒng)計(jì)字符串中空格的數(shù)量，然后進(jìn)行擴(kuò)容，然后從后往前進(jìn)行賦值，這樣在線性時(shí)間內(nèi)即可完成；如果輸入?yún)?shù)為不可變的 String，就不能使用 setLength() 方法，所以用此方法效率會(huì)更慢（String 轉(zhuǎn)為遍歷 StringBuilder； setLength方法執(zhí)行也很慢，其內(nèi)部擴(kuò)容主要調(diào)用 Arrays.copyOf() 和 Arrays.fill()）

class Solution {
    public String replaceSpace(String s) {
        if (s == null || s.length() == 0)
            return "";
        // 劍指Offer
        StringBuilder sb = new StringBuilder(s);
        int count = 0, oldLength = sb.length();
        for (int i = 0; i < oldLength; ++i) {
            if (sb.charAt(i) == ' ')
                count++;
        }
        int newLength = oldLength + count * 2, idx = newLength - 1;
        sb.setLength(newLength);
        for (int i = oldLength - 1; i >= 0; --i) {
            char c = sb.charAt(i);
            if (c == ' ') {
                sb.setCharAt(idx--, '0');
                sb.setCharAt(idx--, '2');
                sb.setCharAt(idx--, '%');
            } else {
                sb.setCharAt(idx--, c);
            }
        }

        return sb.toString();
    }
}

知識(shí)點(diǎn)

String、StringBuffer和StringBuilder的相似點(diǎn)與不同點(diǎn)：

• 運(yùn)行速度，或者說是執(zhí)行速度，在這方面運(yùn)行速度快慢為：StringBuilder > StringBuffer > String；String為字符串常量，而StringBuilder和StringBuffer均為字符串變量，即String對(duì)象一旦創(chuàng)建之后該對(duì)象是不可更改的，但后兩者的對(duì)象是變量，是可以更改的。
• 線程安全；在線程安全上，StringBuilder是線程不安全的，而StringBuffer是線程安全的；如果一個(gè)StringBuffer對(duì)象在字符串緩沖區(qū)被多個(gè)線程使用時(shí)，StringBuffer中很多方法可以帶有synchronized關(guān)鍵字，所以可以保證線程是安全的，但StringBuilder的方法則沒有該關(guān)鍵字，所以不能保證線程安全，有可能會(huì)出現(xiàn)一些錯(cuò)誤的操作。
• String：適用于少量的字符串操作的情況；StringBuilder：適用于單線程下在字符緩沖區(qū)進(jìn)行大量操作的情況；StringBuffer：適用多線程下在字符緩沖區(qū)進(jìn)行大量操作的情況