字符串——替换空格

剑指 Offer 05. 替换空格

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

示例 1：

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

限制：

0 <= s 的长度 <= 10000

思路

方法1——利用额外空间

另外建立一个字符串，然后遍历原字符串
优点：简单
缺点：需要额外空间

方法2——双指针

1. 计算有多少空格
2. 利用resize函数扩大数组大小
3. i指针指向原结尾
   j指针指向新结尾
4. 不是空格原值赋值，空格赋%20

从后面开始：时间复杂度o(n)
只需要遍历原数组一遍
从前面开始：时间复杂度o(n^2)
遍历原数组一遍，向后移位需要再遍历一遍

代码

class Solution {
public:
    string replaceSpace(string s) {
        int oldsize=s.size();
        int newsize=s.size();
        for(int i=0;i<s.size();i++)
        {
            if(s[i]==' ')
            newsize+=2;
        }
        s.resize(newsize);
        for(int i=oldsize-1,j=newsize-1;i<j;)
        {
            if(s[i]!=' ')
            {
                s[j--]=s[i--];
            }
            else
            {
                s[j--]='0';
                s[j--]='2';
                s[j--]='%';
                i--;
            }
        }
        return 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
26
27
28
29