剑指offer——面试题5：替换空格

1.题目描述：

请实现一个函数，把字符串中的每个空格替换成%20。例如，输入“we are happy.”，输出"we%20are%20happy."。

2.解题思路：

可以先遍历数组，统计出空格的个数，则新字符串的长度 = 旧字符串的长度 + 2 * 空格个数。然后使用双指针法，指针p1指向旧字符串的末尾，指针p2指向新字符串的末尾，从后往前进行拷贝。如果p1指向的字符为空格，则向p2所在的位置拷贝0、2、%，再递减指针。

3.代码实现：

public class Offer_5 {
    public static void main(String[] args) {
        String str = "we are happy.";
        System.out.println(ReplaceBlack(str));
    }

    private static String ReplaceBlack(String str) {
        int numOfBlack = 0;
        int p1, p2;

        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ' ') {
                numOfBlack++;
            }
        }
        p1 = str.length() - 1;
        p2 = 2 * numOfBlack + str.length();
        char[] result = new char[p2 + 1];

        while (p1 >= 0 && p2 >= p1) {
            if (str.charAt(p1) == ' ') {
                result[p2--] = '0';
                result[p2--] = '2';
                result[p2--] = '%';
                p1--;
            } else {
                result[p2--] = str.charAt(p1--);
            }
        }
        return String.valueOf(result);
    }
}

这个题如果要申请新的数组，其实用从前往后拷贝的方法也可以，若是输入参数为指针，则可以利用指针偏移的方式，不必再重新申请空间。

复杂度分析：

• 时间复杂度：O(n)，字符长度为n，则总的时间复杂度为O(n).
• 空间复杂度：O(n)，需要额外开辟长度为2n+空格个数大小的空间，总的空间复杂度为O(n)。