《剑指offer刷题笔记》4、替换空格【c++详细题解】

系统管理员 2021-07-24 21:16 365阅读 0赞

### **题目** ###

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

你可以假定输入字符串的长度最大是 1000。

注意输出字符串的长度可能大于 1000。

**样例**

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

### **思路1** ###

**(线性扫描)**  O ( n ) O(n) O(n)

这个题在C++里比较好做，我们可以从前往后枚举原字符串：

如果遇到空格，则在string类型的答案中添加 `"%20"`；  
如果遇到其他字符，则直接将它添加在答案中；  
但在C语言中，我们没有string这种好用的模板，需要自己malloc出char数组来存储答案。  
此时我们就需要分成三步来做

1.  遍历一遍原字符串，计算出答案的最终长度；
2.  malloc出该长度的char数组；
3.  再遍历一遍原字符串，计算出最终的答案数

**时间复杂度分析**  
原字符串只会被遍历常数次，所以总时间复杂度是  O ( n ) O(n) O(n)。

### **代码1** ###

class Solution { 
    public:
        string replaceSpaces(string &str) { 
            string res;
            int len = str.size();
            for(int i = 0;i < len;i++)
            { 
                if(str[i] == ' ') res += "%20";
                else res += str[i];
            }
            return res;
        }
    };

### **思路2** ###

**(双指针扫描)**  O ( n ) O(n) O(n)  
在部分编程语言中，我们可以动态地将原数组长度扩大，此时我们就可以使用双指针算法，来降低空间的使用：

1.  首先遍历一遍原数组，求出最终答案的长度`length`；
2.  将原数组`resize`成`length`大小；
3.  使用两个指针，指针`i`指向原字符串的末尾，指针`j`指向length的位置；
4.  两个指针分别从后往前遍历，如果`str[i] == ' '`，则指针j的位置上依次填充`'0', '2', '%'`，这样倒着看就是`"%20"`；如果`str[i] != ' '`，则指针`j`的位置上填充该字符即可。  
    由于i之前的字符串，在变换之后，长度一定不小于原字符串，所以遍历过程中一定有`i <= j`，这样可以保证`str[j]`不会覆盖还未遍历过的`str[i]`，从而答案是正确的。

**时间复杂度分析**  
原字符串只会被遍历常数次，所以总时间复杂度是  O ( n ) O(n) O(n)。

### **代码2** ###

class Solution { 
    public:
        string replaceSpaces(string &str) { 
    
            int len = 0;
            for (auto c : str)
                if (c == ' ')
                    len += 3;
                else
                    len ++ ;
    
            int i = str.size() - 1, j = len - 1;
    
            str.resize(len);
    
            while (i >= 0)
            { 
                if (str[i] == ' ')
                { 
                    str[j -- ] = '0';
                    str[j -- ] = '2';
                    str[j -- ] = '%';
                }
                else str[j -- ] = str[i];
                i -- ;
            }
            return str;
        }
    };