题目描述

为了防止爬虫，请扫码关注公众号，发送「PP3361」获取下载链接

剑指 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();
    }

}

补充（举一反三）

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