剑指Offer系列（java版，详细解析）05.替换空格

旧城等待， 2022-11-07 04:15 59阅读 0赞

# 题目描述 #

#### [剑指 Offer 05. 替换空格][Offer 05.] ####

难度简单80

请实现一个函数，把字符串 `s` 中的每个空格替换成"%20"。

**示例 1：**

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

**限制：**

0 <= s 的长度 <= 10000

#  #

# 测试用例 #

*  输入的字符串包含空格（空格位于字符串的最前面；空格位于字符串的最后面；空间位于字符串的中间；字符串中有连续多个空格）。
 *  输入的字符串没有空格。
 *  特殊输入测试（字符串为空指针；字符串是一个空字符串）

# 题目考点 #

*  考察应聘者对字符串的编程能力。
 *  考察应聘者分析时间效率的能力、我们要能清晰的分析出两种不同方法的时间效率各是多少。
 *  考察应聘者对 **内存覆盖以及StringBuild长度随append的动态改变** 是否有高度的警惕。
 *  考察应聘者的思维能力，在从前到后替换的思路被面试官否定后，我们能迅速想到从后往前替换的方法。

# 解题思路 #

## 差（时间复杂度为O(N2)） ##

从头到尾扫描字符串，每次遇到空格字符的时候进行替换，由于是把 1 个字符替换成 3 个字符，我们必须要把后面的所有字符都后移2个字节，否则就有两个字符被覆盖了。

**PS 时间复杂度分析：**  
假设字符串的长度为 n 。对于每个空格字符，需要移动后面O(N)个字符，因此对于含有O(N)个空格字符的字符串来说，总的时间复杂度就是O(N2)。

## 好（时间复杂度为O(N)） ##

在字符串尾部填充任意字符，使得字符串的长度等于字符串替换之后的长度。因为一个空格要替换成三个字符（%20），因此当遍历到一个空格时，需要在尾部填充两个任意字符。

准备两个指针：P1 和 P2，令 P1 指向字符串原来的末尾位置，P2 指向字符串现在的末尾位置。P1 和 P2从后向前遍历，当 P1 遍历到一个空格时，就需要令 P2 指向的位置依次填充 02%（注意是逆序的），否则就填充上 P1 指向字符的值。知道 P1 和 P2 指向同一位置。

# 自己解题 #

/** * Author:Viper * Data:2021/3/10 * description: */
    public class problem05 { 
        public String replaceSpace(String s) { 
            StringBuilder res = new StringBuilder();
            for(Character c : s.toCharArray()){ 
                if(c==' ')res.append("%20");
                else res.append(c);
            }
            return res.toString();
        }
    }

解题缺陷：

1.  只是达到了解题的目的。

# 正确解题 #

/** * 替换空格 * 从后往前（降低时间复杂度） */
    public class Solution1 { 
        /** * @Description 替换空格 * 利用两个指针从后往前替换 * @param str 输入字符串 */
        public static String replaceSpace(StringBuffer str) { 
            if (str == null) { 
                return null;
            }
            int oldLength = str.length();
            // 扩展StringBuffer
            for (int i = 0; i < oldLength; i++) { 
                if (str.charAt(i) == ' ') { 
                    str.append(" ");
                }
            }
            int newLength = str.length();
            int p1 = oldLength - 1;
            int p2 = newLength - 1;
            while (p1 != p2) { 
                if (str.charAt(p1) == ' ') { 
                    str.setCharAt(p2--, '0');
                    str.setCharAt(p2--, '2');
                    str.setCharAt(p2--, '%');
                    p1--;
                } else { 
                    str.setCharAt(p2--, str.charAt(p1--));
                }
            }
            return str.toString();
        }
    
    }

# 补充（举一反三） #

在合并两个数组（包括字符串）时，如果从前往后复制每个数字（或字符）需要重复移动数字（或字符）多次时，我们可以考虑从后往前复制，这样能减少移动次数，从而提高效率。

[Offer 05.]: https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/