替换空格（Java实现）

替换空格（Java实现）

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

思路： 考虑时间复杂度为O(n)的解法，搞定Offer就靠它了

我们先遍历一次字符串，这样就能够统计出字符串中空格的综述，并可以计算出替换之后字符串的总的长度。每替换一个空格，长度增加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)，比第一个思路要快。

我这里偷懒了，直接用了String类中的replaceAll方法，代码实现不重要，重要的是掌握思路。

package Day39;
/**
 * @Author Zhongger
 * @Description 请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
 * @Date 2020.3.11
 */
public class ReplaceBlankClass {
    public static void main(String[] args) {
        ReplaceBlankClass replaceBlankClass = new ReplaceBlankClass();
        StringBuffer stringBuffer = new StringBuffer("We are happy!");
        System.out.println(replaceBlankClass.replaceSpace(stringBuffer));
    }
    public String replaceSpace(StringBuffer str) {
        return str.toString().replaceAll(" ","%20");
    }
}