【题解】剑指 Offer 05. 替换空格 (C 语言)

2022 年 6 月 14 日
本文字数：2632 字
阅读完需：约 9 分钟

⭐️题目概要⭐️

请实现一个函数，把字符串s中的每个空格替换成"%20"。

📒博客主页：https://www.infoq.cn/profile/D47E9FD34A2AE2/publish
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创！
📆InfoQ 首发时间：🌴2022 年 6 月 14 日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《数据结构与算法》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

⭐️剑指 Offer 05. 替换空格⭐️

请实现一个函数，把字符串s中的每个空格替换成"%20"。

示例：

输入：s = "We are happy."输出："We%20are%20happy."

复制代码

限制：

0 <= s 的长度 <= 10000

复制代码

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/

⭐️解题思路⭐️

在网络编程中，如果URL参数中含有特殊字符，如空格、#等，则可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在%后面跟上ASCII码的两位十六进制的表示。比如空格的 ASCII码是 32，即十六进制的 0x20，因此空格被替换成"%20"。再比如#的 ASCII码为 35，即十六进制的 0x23，它在 URL中被替换为"%23"。

看到这个题目，我们首先应该想到的是原来一个空格字符，替换之后变成'%'、'2'和'0'这 3 个字符，因此字符串会变长。如果是在原来的字符串上进行替换，就有可能覆盖修改在该字符串后面的内存。如果是创建新的字符串并在新的字符串上进行替换，那么我们可以自己分配足够多的内存。由于在力扣在线平台上 C 语言提供的是一个常量的字符串，不能再原地进行修改，所以本文采用创建新的字符串变量并在上面进行替换。

要创建一个新的字符串变量，就考虑申请多少的空间，假设输入的字符串长度为len，你可以不经思考地申请一块3*len + 1大小的空间，因为当这个字符串全部是空格时替换后的长度就变为了3*len，考虑到还有一个\0，所以替换后的字符串长度最大为3*len+1（包括\0）。但是对于新空间的开辟，坚持“用多少开多少的原则”，我们可以先遍历一遍原字符串，计算出空格字符的数量cnt，原来是一个字符替换后变为三个字符，相当于增加了俩个字符，再加上最后的\0，所以需要给替换后的新字符串长度开辟的空间为len + cnt*2 + 1。

开辟好足够的空间后，就是字符串的替换了。

对于这道题，博主给出 3 种解题方法：

方法 1： 先将输入的字符串拷贝，然后在拷贝的字符串变量上进行替换修改。对该字符串进行遍历，遇到空格将空格后的所有字符向后移动两位，然后将空格替换为%20。

时间复杂度： O(N^2^)

方法 2： 先将输入的字符串拷贝，然后在拷贝的字符串变量上进行替换修改。与方法 1 不同的是这次准备两个指针，一个指向原来字符串\0的位置记为left，另一个指向新申请字符串变量中将空格替换后\0的位置记为right。（<font color=red>这就表示新申请的空间要刚刚合适或者需要计算空格数量得到新的\0的位置</font>）然后将left指向的字符移动到right所指向的空间，从后往前遍历，当left遇到空格时将right向前移动 3 次，插入%20。直到left = right。当两个指针相等时，表示字符串替换完毕。

时间复杂度： O(N)

方法 3： 边进行字符串拷贝边进行空格替换。对新旧两个字符串同时进行遍历，如果原来的字符串遇到空格，就在新字符串后插入%20。

时间复杂度： O(N)

源代码

编程语言：C 语言在线编程平台：力扣

//方法1char* replaceSpace(char* s){    int len = strlen(s);    int m = 0;    int cnt = 0;    for (m = 0; m < len; m++)    {        if (*(s + m) == ' ')        {            cnt++;        }    }    //char* str = (char*)malloc(sizeof(char)*3*len + 1);//申请足够的空间    char* str = (char*)malloc(sizeof(char) * (len + cnt * 2 + 1));//申请足够多的空间    strcpy(str,s);//拷贝字符串    int i = 0;    char rep[3] = {'%', '2', '0'};    while (*(str + i) != '\0')    {        int right = len;            if (*(str + i) == ' ')            {                len = len + 2;                while (right > i)                {                    *(str + right + 2) = *(str + right);//移动空格后元素                    right--;                }                int j = 0;                while(right < i + 3)                {                    *(str + right)  = *(rep + j);//替换空格                    right++;                    j++;                }                i += 2;            }            i++;    }    return str;}

复制代码

//方法2char* replaceSpace(char* s){    int len = strlen(s);    int m = 0;    int cnt = 0;    for (m = 0; m < len; m++)    {        if (*(s + m) == ' ')        {            cnt++;        }    }    char* str = (char*)malloc(sizeof(char) * (len + cnt * 2 + 1));//申请足够多的空间    int left = len;    int right = len + cnt*2;    strcpy(str,s);//拷贝字符串    while(left >= 0 && left < right)    {        if (*(str + left) == ' ')        {            *(str + right) = '0';            right--;            *(str + right) = '2';            right--;            *(str + right) = '%';            right--;        }        else        {            *(str + right) = *(str + left);            right--;        }        left--;    }    return str;}

复制代码

//方法3char* replaceSpace(char* s){    int len = strlen(s);    int m = 0;    int cnt = 0;    for (m = 0; m < len; m++)    {        if (*(s + m) == ' ')        {            cnt++;        }    }    char* str = (char*)malloc(sizeof(char) * (len + cnt * 2 + 1));//申请足够多的空间    int i = 0;    int j = 0;    for (i = 0; i < len; i++, j++)    {        *(str + j) = *(s + i);//拷贝字符        if (*(s + i) == ' ')        {            *(str + j) = '%';            j++;            *(str + j) = '2';            j++;            *(str + j) = '0';//遇到空格则替换字符        }    }    *(str + j) = '\0';    return str;}