程序员社区

剑指Offer系列(java版,详细解析)05.替换空格

题目描述

剑指Offer系列(java版,详细解析)05.替换空格插图

为了防止爬虫,请扫码关注公众号,发送「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();
    }

}

补充(举一反三)

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

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 剑指Offer系列(java版,详细解析)05.替换空格

一个分享Java & Python知识的社区