LeetCode.剑指offer.05

面试题05. 替换空格

解法一：

java自带的字符串替换方法：

[String replace(char oldChar, char newChar)]

class Solution {
    public String replaceSpace(String s) {
        return s.replace(" ","%20");
    }
}

执行用时 :2 ms, 在所有 Java 提交中击败了30.81% 的用户

内存消耗 :34.6 MB, 在所有 Java 提交中击败了100.00%的用户

但是时间复杂度不是很理想（顺便看看replace的源码?）

public String replace(char oldChar, char newChar) {
        if (oldChar != newChar) {
            int len = value.length;
            int i = -1;
            char[] val = value; /* avoid getfield opcode */
			//避免字符串中没有oldchar浪费资源
            while (++i < len) {
                if (val[i] == oldChar) {
                    break;
                }
            }
            if (i < len) {
                char buf[] = new char[len];
                for (int j = 0; j < i; j++) {
                    buf[j] = val[j];
                }
                while (i < len) {
                    char c = val[i];
                    buf[i] = (c == oldChar) ? newChar : c;
                    i++;
                }
                return new String(buf, true);
            }
        }
        return this;
    }

解法二：

新建一个StringBuilder进行存储，遍历原字符串遇到空格替换成“%20”即可；

时间复杂度:O(n)

class Solution {
    public String replaceSpace(String s) {
        StringBuilder stringBuilder = new StringBuilder();
        for(int i = 0;i < s.length();i++){
            char tmp = s.charAt(i);
            if(tmp == ' '){
                stringBuilder.append("%20");
            } else{
                stringBuilder.append(tmp);
            }
        }
        return stringBuilder.toString();
    }
}

执行用时 :0 ms, 在所有 Java 提交中击败了100.00% 的用户

内存消耗 :40.1 MB, 在所有 Java 提交中击败了100.00%的用户

解法三：

本题的原意应是不利用额外空间，在原数组上进行修改。

public class Solution {
    public String replaceSpace(StringBuffer str) {
    	int len1 = str.length() - 1;
        for(int i = 0; i <= len1; i++){
            if(str.charAt(i) == ' '){
                str.append("  ");
            }
        }
        int len2 = str.length() - 1;
        while(len2 > len1 && len1 >= 0){
            char c = str.charAt(len1--);
            if(c == ' '){
                str.setCharAt(len2--, '0');
                str.setCharAt(len2--, '2');
                str.setCharAt(len2--, '%');
            }else{
                str.setCharAt(len2--, c);
            }
        }
        return str.toString();
    }
}