剑指Offer_4_替换空格

2017-03-14

题目描述

请实现一个函数，把字符串中的每个空格替换成 %20 。例如输入”We are happy”，则输出”We%20are%20happy”
不能用java的一些api，完全用C语言的方式完成本题，不然会被鄙视。

解题思路
虽然我们可以使用遍历的方式，创建一个新的空数组来完成这道题，时间复杂度也只是O(n)，但是浪费了很多空间。
虽然我们可以正序遍历数组，每碰到一个空格，就将后边的所有元素向后移动，这样虽然不用开辟冗余的空间，但是时间复杂度较高，
最后一部分元素需要被移动 N*空格数次。

如果我们采用倒序的方式遍历和移动数组，那么时间复杂的和空间复杂度都是最低的。

先遍历一次字符串，统计空格出现的次数，每出现一个空格，对改数组额外开辟2位。
从字符串的后面开始复制和替换。
- 指针P1指向原始字符串末尾，指针P2指向开辟空间后字符串末尾
- P1向前移动，逐个把字符复制到P2，直到碰到空格为止
- 碰到空格后，P1向前移动一位，P2向前移动三位的同时将%20填充
- 当P2追赶上P1时，结束复制，表示所有空格已经替换完毕

代码实现

public class CharReplace
{
    public static char[] replaceSpace(char[] str,int length)
    {
        if (str == null)
            return null;
        // 计算总共有多少个空格
        int spaceCount = 0;
        for (int i = 0; i < str.length; i++)
        {
            if (str[i] == ' ')
                spaceCount++;
        }
        // 扩展字符数组长度,每个 ' ' 替换为 %20 需要额外扩展2个长度
        for (int i = 0; i < spaceCount; i++)
        {
            str = (String.valueOf(str) + "  ").toCharArray();
        }
        // 两个指针，P1指向元数组结尾，P2指向新数组结尾
        int p1 = length - 1;
        int p2 = str.length - 1;
        // 从p1向前，逐步将字符复制到p2
        while (p1 != p2)
        {
            // 如果p1为空格，则p1向前移动1位，p2向前移动三位并填充%20
            if (str[p1] == ' ')
            {
                p1--;
                str[p2--] = '0';
                str[p2--] = '2';
                str[p2--] = '%';
            }
            else
            {
                str[p2--] = str[p1--];
            }
            System.out.println(p1 + "," + p2 + "   " + String.valueOf(str));
        }
        return str;
    }
    public static void main(String[] args)
    {
        char[] str = "We are happy  ~~~".toCharArray();
        System.out.println(replaceSpace(str,str.length));
    }
}