剑指Offer——替换字符串中空格 Java

题目描述

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

Java知识点（String StringBuffer StringBuilder）

1. 运行速度 StringBuilder > StringBuffer > String

通俗来讲 String定义的是一个常量，每一次对str的使用 都会涉及到JVM对string 的创建 回收

比如 str = ‘abc’ str = str+'de'

虽然感觉str没变，但是底层是先 创建了一个str 并赋值 之后 将原来的str 垃圾回收

2. 再来说线程安全

在线程安全上，StringBuilder是线程不安全的，而StringBuffer是线程安全的

如果一个StringBuffer对象在字符串缓冲区被多个线程使用时，StringBuffer中很多方法可以带有synchronized关键字，所以可以保证线程是安全的，但StringBuilder的方法则没有该关键字，所以不能保证线程安全，有可能会出现一些错误的操作。所以如果要进行的操作是多线程的，那么就要使用StringBuffer，但是在单线程的情况下，还是建议使用速度比较快的StringBuilder。

3. 总结一下

   String：适用于少量的字符串操作的情况

   StringBuilder：适用于单线程下在字符缓冲区进行大量操作的情况

   StringBuffer：适用多线程下在字符缓冲区进行大量操作的情况

解题思路

逐个检测，非空格 就直接 append 到temp后边，如果是空格 就将%20 append到temp的后边。（temp 是要 返回的 字符串）

关键： 检测到的是 char 的 空格 要替换成 字符串的 “%20”

    public String replaceSpace(StringBuffer str) {
        StringBuffer temp = new StringBuffer();
        for (int i = 0; i < str.length(); i++) {
            char a = str.charAt(i);
            if (Character.isWhitespace(a)){
                temp.append("%20");
                continue;
            }
            temp.append(a);
        }

        return temp.toString();
    }

上述只是针对牛客网的题解。

对于《剑指》里面给出的方法，条件是原字符串长度足够长，则可以再原字符串上进行操作，从后向前，依次挪动字符串并填补‘%’、‘2’、‘0’

从后向前操作 时间复杂度O(N)
对于数组问题，很方便的能索引到任意下标，从后向前操作会方便很多。对于本题来说，《剑指》中的解法，从前向后会存在冗余的移动。而从后向前操作就避免了。

类似的题：合并两个排序字符串，从后向前操作也是最优的。