不忘初心

少年,专心练剑吧

替换空格

发表于 更新于 分类于

题目

请实现一个函数，把字符串中的每个空格替换成”%20”。
样例
给定 “We are happy” 返回 “We%20are%20happy.”

分析

先遍历一次字符串，统计出字符串中空格的总数，由此可以确定替换之后的字符串的总长度。
从字符串的最后开始复制和替换。所有的字符都只移动一次，算法的时间效率是O(n)。

代码（cpp）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void ReplaceBlank(char string[], int length)
{
        if(string == NULL || length <= 0)
            return;
        int originalLength = 0;
        int numberOfBlank = 0;
        int i = 0;
        while(string[i] != '\0')
        {
            ++originalLength;
            if(string[i] == ' '){
                ++numberOfBlank;
            }
            ++i;
        }

        int newLength = originalLength + numberOfBlank * 2;
        if(newLength > length)
            return ;
        int indexOfOriginal = originalLength;
        int indexOfNew = newLength;
        while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
        {
            if(string[indexOfOriginal] == ' ')
            {
                string[indexOfNew--] = '0';
                string[indexOfNew--] = '2';
                string[indexOfNew--] = '%';
            }else
            {
                string[indexOfNew--] = string[indexOfOriginal];
            }
            --indexOfOriginal;
        }
}