23°

迷人的算法-剑指offer面试题5:替换空格

文中源码链接,欢迎star,共同维护代码:https://github.com/caozhixin/algorithms-and-data-structures

    题目:请实现一个函数,把字符串中的每个空格替换成"%20"。
例如,输入"We are happy.",则输出"We%20are%20happy."。

此题看似简单,实则坑还是比较多的。

替换字符的长度有变化,由空格‘ ’一个字符变成”%20“三个字符,这样势必会造成原字符串长度变长,这样就要考虑字符数组长度是否够用(当然java中String字符串的变更都是创建新的字符串常量,此处字符串视为字符数组。)

除了数组长度会发生变化,这其中还涉及到一个字符替换成三个字符后,原位置字符的移动问题(不移动会造成替换字符覆盖原字符问题),为避免同一字符多次移动的操作(O(n^2)),这里可以采用从后向前替换的操作(O(n))。

当然如果空间允许的情况下,重新创建一个字符串来得更快(显然这样会和offer擦肩而过...)。

 

taking is cheaper,show the code.

/**
 * 〈面试题5:请实现一个函数,把字符串中的每个空格替换成"%20"。
 * 例如,输入"We are happy.",则输出"We%20are%20happy."。〉
 *
 * @author caozx
 * @date 2020/1/16 17:47
 */
public class Question05 {
/**
 * 方式一:开辟新空间
 */
public String replaceBlank1(String s) {
    if (s == null) {
        return null;
    }

    StringBuilder stringBuilder = new StringBuilder();
    // 遍历字符串, 复制每个字符, 当遇到空格时, 就增加替换字符。
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == ' ') {
            stringBuilder.append("%20");
        } else {
            stringBuilder.append(c);
        }
    }

    return stringBuilder.toString();
}

/**
 * 方式二:从后往前复制
 */
public String replaceBlank2(String s) {
    if (s == null) {
        return null;
    }

    StringBuilder stringBuilder = new StringBuilder(s);

    // 记录空格数
    int blankNum = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == ' ') {
            blankNum++;
        }
    }

    int sEndIndex = s.length() - 1;
    int newStringEndIndex = s.length() - 1 + 2 * blankNum;
    stringBuilder.setLength(newStringEndIndex + 1);
    while (sEndIndex < newStringEndIndex) {
        if (s.charAt(sEndIndex) == ' ') {
            stringBuilder.setCharAt(newStringEndIndex--, '0');
            stringBuilder.setCharAt(newStringEndIndex--, '2');
            stringBuilder.setCharAt(newStringEndIndex--, '%');
        } else {
            stringBuilder.setCharAt(newStringEndIndex--, s.charAt(sEndIndex));
        }
        sEndIndex--;

    }

    return String.valueOf(stringBuilder);
}

}

测试:

public class Quention05Test {
public static void main(String[] args) {
    String s = "helle world, my name is caozx.";
    String s1 = "helleworld.";
    Question05 question05 = new Question05();
    System.out.println(question05.replaceBlank1(s));
    System.out.println(question05.replaceBlank1(null));
    System.out.println(question05.replaceBlank1(s1));
    System.out.println(question05.replaceBlank2(s));
    System.out.println(question05.replaceBlank2(null));
    System.out.println(question05.replaceBlank2(s1));

}

}

 

本文由【A_laoshiren】发布于开源中国,原文链接:https://my.oschina.net/u/3730932/blog/3159244

全部评论: 0

    我有话说: