力扣×剑O 05. 替换空格

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

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

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

限制：
0 <= s 的长度 <= 10000

实在想不出有什么特殊技巧，用最简单的方法纯手动实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string replaceSpace(string s) {
        string str;
        for(auto i:s){
            if(i==' '){
                str+="%20";
                continue;
            }
            str+=i;
        }
        return str;
    }
};
运行效果

如果没有限制，那么上面的代码已经足够了。但是可能会要求在原来的字符串上进行替换，如果要求了，那么这种方法不合适。

由于有两种不同的解决方案，我们应该向面试官问清楚 ，让他明确告诉我们他的需求。假设面试官让我们在原来的字符串上进行替换，并且保证输入的 字符串后面有足够多的空余内存。

后面根据原来的字符串上进行替换的要求，列举了两个例子：
第一个是较差的时间复杂度为O(n^2)的解法，即每次替换将空格后面的字符全部向后移动两个位置；
第二种效率较高，时间复杂度为O(n)，同时因为空间占用也更低，是这三种中最好的方法。

总体思路：第一次遍历计算出替换之后的字符串的总长度并扩充，第二次利用两个指针p1、p2分别指向原字符串和替换后字符串的末尾，从尾到头进行复制。遇到普通字符直接复制过来并前移一格，遇到空格p1前移一个、p2填充字符并前移三格。

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:
    string replaceSpace(string s) {
        int originalNum=s.size()-1,newNum=0; //originalNum旧字符串最后一个字符位置
        auto poriginal = s.end()-1;  //指向原字符串尾
        for(auto i:s){
            if(i==' ')
                ++newNum;   //空格数量
        }
        newNum=s.size()+newNum*2;  //扩充后长度
        s.resize(newNum);
        --newNum;    //指向新字符串最后一个字符位置
        while(originalNum>=0){
            if(s[originalNum]!=' ')
                s[newNum--] = s[originalNum--];   //复制旧字符到新位置，都前移一位
            else{
                s[newNum--] = '0';//填充三个新字符，移动三位
                s[newNum--] = '2';
                s[newNum--] = '%';
                --originalNum;//旧位置只前移一位
            } 
        }
        return s;
        }
};

因为书上代码用的是c语言，采用字符数组的形式。string如果要重新分配大小（resize），很可能会把原来的字符串移动到一个新位置，这样resize前指向原来字符串末尾的指针就变成了一个指向未知地方的指针。除非记住原来字符串中字符个数num，resize之后通过s.begin()+num来获得原来最后一个字符的位置。