hlwang's Blog

理想主义青年永远不会被现实招安

0%

剑指 Offer 05. 替换空格

发表于 更新于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目描述

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

示例

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

限制：

1
0 <= s 的长度 <= 10000

解题思路

1
2
3
4
5
6
7
8
思路：双指针
遍历一遍找出字母的数量，空格的数量
字符串长度为 字母的数量+空格的数量
将字符串扩充到 字母的数量+空格的数量 * 3
p从原来的最后一个字符开始往前遍历，q从末尾开始
当p指向的值不为空格时，复制到q，pq往前移
当p指向的值为空格时，q，q-1，q-2替换为 "%20"
直到遍历完成

代码

核心代码实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution
{
public:
    string replaceSpace(string s)
    {
        // 判空
        if (s.empty())
        {
            return s;
        }
        // 定义字符长度
        int lenOfAlphabet = 0;
        // 定义空格数量
        int lenOfSpace = 0;
        // 计算字符串长度
        int n = s.size();
        // 遍历字符串
        for (int i = 0; i < n; i++)
        {
            // 如果是空格
            if (s[i] == ' ')
            {
                // 空格数量+1
                lenOfSpace++;
            }
            else
            {   
                // 否则字母数量+1
                lenOfAlphabet++;
            }
        }
        // 如果没有空格,不需要替换,return就行
        if (lenOfSpace == 0)
        {
            return s;
        }
        // 每有一个空格,字符串就摇扩容两个空间
        for (int i = 0; i < lenOfSpace; i++)
        {
            s = s + "  ";
        }
        // 定义p为原字符串最后一个,q为新字符串最后一个
        int p = n - 1, q = lenOfAlphabet + lenOfSpace * 3 - 1;
        // 循环条件为p>=0,也就是遍历没完成
        while (p >= 0)
        {
            // 如果等于空格,则q,q-1,q-2替换为 "%20"
            if (s[p] == ' '){
                s[q--] = '0';
                s[q--] = '2';
                s[q--] = '%';
                // p往前移
                p --;
                
            }
            // 否则复制p到q
            else{
                s[q--] = s[p--];
            }
        }
        // 返回
        return s;
    }
};

main函数

1
2
3
4
5
6
7
8
int main(int argc, char const *argv[])
{
    string s = "We are happy.";
    Solution s1;
    string ans = s1.replaceSpace(s);
    cout << "ans: " << ans << endl;
    return 0;
}

通过截图

image-20230116112740422