[剑指Offer] 两种方法求解空格替换

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

1）需要我们手动开辟空间

• 遍历一遍字符串，计算空格的个数，然后重新初始化一个新的字符串，再对原字符串进行遍历，若不为空格，直接插入，若为空格，依次插入%20这三个字符。

char* replaceSpace(char* s ) {
    int len1 = strlen(s);
    int count = 0;
    for(int i=0; i<len1; i++){
        if(s[i] == ' ')
            count++;
    }
    
    int len2 = len1+2*count;
    char* str = (char*)malloc(len2);
    int j=0;
    for(int i=0; i<len1; i++){
        if(s[i] == ' '){
            str[j++] = '%';
            str[j++] = '2';
            str[j++] = '0';
        }
        else{
            str[j++] = s[i];
        }
    }
    return str;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2）字符串空间足够的情况

• 先计算空格的个数，然后计算替换空格之后的字符串长度。使用新旧两个指针分别指向替换空格之前和之后的字符串的尾部，然后依次从尾部进行遍历，遇到空格就替换，否则继续向前遍历，直到两个尾指针相遇，替换结束。

void replaceSpace(char *str,int length) {
        if(str==nullptr || length==0)
            return;
         
        char* p = str;
        int count = 0;
        while(*p != '\0'){
            if(*p == ' ')
                count++;
            p++;
        }
         
        char* end1 = str+length-1;
        char* end2 = str+length+2*count-1;
        while(end1 != end2){
            if(*end1 != ' '){
                *(end2--) = *(end1--);
            }
            else{
                *(end2--) = '0';  //注意：从后向前替换
                *(end2--) = '2';
                *(end2--) = '%';
                end1--;
            }
        }
    }
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