剑指Offer05:替换空格

剑指Offer05:替换空格

Scroll Down

剑指Offer:替换空格

题目

题目链接

剑指Offer:替换空格

题目描述

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

分析

这道题很简单。

方法一:直接是用自带函数(replace)进行替换

代码:

public class Solution {
    public String replaceSpace(StringBuffer str) {
        return str.toString().replace(" ", "%20");
    }
}
或
public class Solution {
    public String replaceSpace(StringBuffer str) {
        StringBuffer stringBuffer = new StringBuffer();
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ' ') {
                stringBuffer.append("%20");
            }else {
                stringBuffer.append(str.charAt(i));
            }
        }
        return stringBuffer.toString();
    }
}

方法二:利用双指针法

我们先遍历一次字符串,这样就能够统计出字符串中空格的综述,并可以计算出替换之后字符串的总的长度。每替换一个空格,长度增加2,因此替换以后的字符串的长度等于原来的长度加上2乘以空格的数目,我们还是以前面的字符串”We are happy"为例,“We are happy"这个字符串的长度是14,里面有两个空格,因此替换之后的字符串的长度为18

我们从字符串的后面开始复制和替换。首先准备两个指针,P1和P2. P1指向原始字符串的末尾,而P2指向替换之后的字符串的末尾。接下来我们向前移动指针P1,逐个把它指向的字符复制到P2指向的位置,直到碰到第一个空格为止。此时字符串包含如下图b所示,灰色阴影的区域是做了字符拷贝的区域。碰到第一个空格之后,把P1向前移动一格,在P2之前插入字符串”%20“,由于”%20“的长度为3,同时也要把P2向前移动3格如图所示。

我们接着向前复制,直到碰到第二个空格(d)所示。和上一次一样,我们再把P1向前移动1格,并把P2向前移动3格插入”%20“(如图e),此时P1,P2指向同一个位置,表明所有的空格都已经替换完毕。

从上面的分析我们可以看出,所有的字符都只复制一次,因此这个算法的时间效率是O(n),比第一个思路要快。

replaceSpace

​ 注: 图中带有阴影的区域表示被移动的字符

  • (a)把笫一个指针指向 宇符串的末尾, 把笫二个指针指向替换之后的字符串的末尾

  • (b)依次复 制字符串的内容, 直至笫一个指针碰到笫一个空格。

  • (c)把笫一个空格替 换成"%20", 把笫一个指针向前移动 I 格, 把笫二个指针向前移动 3格。

  • (d) 依次向前复制字符串中的字符, 直至碰到空格, (e)替换字符串中的倒数笫二个空格, 把第一个指针向前移动I格, 把笫二个指针向前移动3格。

代码:

public class Solution {
    public String replaceSpace(StringBuffer str) {
        //计算空格的数量
        int blankNum = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ' ') {
                blankNum++;
            }
        }
        //记录初始的字符串、插入后的字符串的长度
        int originalStringLength = str.length();
        int newStringLength = originalStringLength + blankNum * 2;
        //重新设置str的长度
        str.setLength(newStringLength);
        //定义两个指针,分别指向新旧字符串的末尾
        int indexOfOriginalString = originalStringLength - 1;
        int indexOfNewString = newStringLength - 1;
        //结束条件及确保是否越界
        while (indexOfOriginalString >= 0 && indexOfNewString > indexOfOriginalString) {
            if (str.charAt(indexOfOriginalString) == ' ') {
                //插入语%20
                str.setCharAt(indexOfNewString--, '0');
                str.setCharAt(indexOfNewString--, '2');
                str.setCharAt(indexOfNewString--, '%');
            } else {
                str.setCharAt(indexOfNewString--, str.charAt(indexOfOriginalString));
            }
            indexOfOriginalString--;
        }
        return str.toString();
    }
}