05. 替换空格

一、题目描述

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

示例 1：

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

限制：

0 <= s 的长度 <= 10000

二、解题思路

由于需要将空格替换为 “%20” ，字符串的总字符数增加，因此需要扩展原字符串 s 的长度，计算公式为：新字符串长度 = 原字符串长度 + 2 * 空格个数

算法流程：

①、初始化：定义空格数量 count = 0 ，通过string.size()计算字符串长度 len ；
②、统计空格数量：遍历 s ，遇空格则 count++ ；
③、修改 s 长度：添加完 “%20” 后的字符串长度应为len + 2 * count；
④、倒序遍历修改：i 指向原字符串尾部元素， j 指向新字符串尾部元素；当 i = j 时跳出（代表左方已没有空格，无需继续遍历）；

​ a、当 s[i] 不为空格时：执行 s[j] = s[i] ；
​ b、当 s[i] 为空格时：将字符串闭区间 [j-2, j] 的元素修改为 “%20” ；由于修改了 3 个元素，因此需要 j -= 2 ；

⑤、返回值：已修改的字符串 s ；

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
class Solution
{
public:
    void replaceSpace(char *str,int length)
    {
        int count=0;
        for(int i=0; i<length; i++) //从前向后
        {
            if(str[i]==' ')
                count++;//记录空格数
        }
        for(int j=length-1; j>=0; j--) //从后向前
        {
            if(str[j]!=' ')
                str[j+2*count]=str[j];
            else
            {
                count--;
                str[j+2*count]='%';
                str[j+2*count+1]='2';
                str[j+2*count+2]='0';
            }
        }
    }
};

三、具体程序实现

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
36
#include<iostream>
#include<cstring>//strlen函数的头文件
using namespace std;
class Solution
{
public:
    void replaceSpace(char *str,int length)
    {
        int count=0;
        for(int i=0; i<length; i++) //从前向后
        {
            if(str[i]==' ')
                count++;//记录空格数
        }
        for(int j=length-1; j>=0; j--) //从后向前
        {
            if(str[j]!=' ')
                str[j+2*count]=str[j];
            else
            {
                count--;
                str[j+2*count]='%';
                str[j+2*count+1]='2';
                str[j+2*count+2]='0';
            }
        }
    }
};
int main()
{
    char str[]="we are happy.";
    Solution s;
    s.replaceSpace(str,strlen(str));//strlen函数测字符数组长度
    cout<<str<<endl;//字符数组直接这样输出就可以
    return 0;
}