【C语言刷题】牛客网刷题——替换空格

题目描述

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

核心代码模式：

void replaceSpace(char *str,int length)
{
    

}

题目这里就是要我们直接修改str指向字符串，按照要求把每一个空格替换成"%20"，length就是所给字符串长度。

思路分析和代码实现（C语言）

1.双指针移位法

我们不创建新的数组，直接对str指向字符串”原地修改“。我们假定要在原字符串基础上增长一段，定义两个指针，end1指向当前字符串末尾处，end2指向增长后的字符串的末尾处，那么要增长多少呢？你想啊，题目说了每个空格要替换成"%20"，也就是由原来的一个字符变成了三个字符，于是每换一次字符串就要增长2个字节，有几个空格就换几次嘛，所以最终要增长2空格数。关于空格数如何得到其实很简单，遍历字符串遇到空格计数即可。
下面就以题目给的例子"We Are Happy.“来讲解。

接下来就让两指针向前移动，如果end1没有遇到空格的话，就把end1指向的字符拷贝到end2指向的位置，要是end1遇到空格了，就让end2的指向从当前位置开始向前分别放入字符’0’、‘2’和’%'。由于需要重复这些过程，我们很容易知道需要套上一个循环，那么循环条件是什么呢？
在两指针向前移动过程中，每轮循环end1都固定地-1，而end2则不同，如果end1没遇到空格，end2同end1一样每轮向前移动一位；要是end1遇到空格，此时end2向前移动了三位（因为要放入”%20"），也就比end1多向前移动了两位，所以总共要多向前移动2空格数位，而一开始end1就比end2靠前2*空格数位，这就是说，最终两个指针会相遇，当它们相遇时说明移位结束，字符串修改完成。所以循环的条件就是end1 != end2。


欸，end1和end2相同时"We"就没有移位呀，是不是有问题啊？别急，你仔细看图，这个时候"We"也就是第一个单词已经不需要再移位了！

代码实现

void replaceSpace(char* str, int length)
{
    
    int space_cnt = 0;
    char* tmp = str;
    while (*tmp)
    {
    
        if (*tmp == ' ')
            space_cnt++;
        tmp++;
    }

    char* end1 = str + length - 1;
    char* end2 = end1 + 2 * space_cnt;

    while (end1 != end2)
    {
    
        if (*end1 != ' ')
        {
    
            *end2-- = *end1--;
        }
        else
        {
    
            end1--;
            *end2-- = '0';
            *end2-- = '2';
            *end2-- = '%';
        }
    }
}

2.辅助数组遍历拷贝

考虑新建一个辅助数组，比原数组要大，我们这里直接莽个两倍，动态开辟内存。遍历原数组，如果没遇到空格的话就把字符原封不动拷贝到辅助数组中，如果遇到空格的话就把"%20"按顺序放入辅助数组中，辅助数组下标得+3，毕竟一次放了三个字符。等遍历完以后，要记得给辅助数组在最后加个’\0’。
最后把辅助数组拷贝到原数组中即可。

代码实现

void replaceSpace(char* s, int len)
{
    
    int cnt = 0;
    char* ret = (char*)calloc(2 * len, sizeof(char));
    char* ptr = s;

    while (*ptr)
    {
    
        if (*ptr != ' ')
        {
    
            ret[cnt] = *ptr;
            cnt++;
        }
        else
        {
    
            ret[cnt] = '%';
            ret[cnt + 1] = '2';
            ret[cnt + 2] = '0';
            cnt += 3;
        }
        ptr++;
    }
    ret[cnt] = '\0';
    strcpy(s, ret);
}