剑指 Offer 05. 替换空格

题目

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

代码

法一、自己写的

 1 class Solution {
 2 public:
 3     string replaceSpace(string s) {
 4         string res;
 5         for(int i = 0;i < s.length();i++){
 6             if(s[i] != ' ') res.push_back(s[i]);
 7             else{
 8                 res.push_back('%');
 9                 res.push_back('2');
10                 res.push_back('0');
11             }
12         }
13         return res;
14     }
15 };

浪费了空间

法二、数组填充问题：双指针+从后向前填充

 1 class Solution {
 2 public:
 3     string replaceSpace(string s) {
 4         int count = 0;
 5         int oldSize = s.size();  //记录原始数组大小
 6         for(int i = 0;i < s.size();i++){
 7             if(s[i] == ' ') count++;
 8         }
 9         s.resize(s.size()+2*count);
10         for(int i = oldSize - 1,j = s.size()-1;i < j;i--){
11             if(s[i]!=' ') {s[j--] = s[i];}
12             else{
13                 s[j--] = '0';
14                 s[j--] = '2';
15                 s[j--] = '%';
16             }
17         }
18         return s;
19     }
20 };

注意：双指针移动的循环终止条件（第十行）是两个指针不重合，而不是 i > 0;

i>0 时的错误例子：空字符串" "

总结

对于数组填充类问题：

1.扩充数组 resize

2.利用双指针从后向前填充

为什么要从后向前填充？

因为每替换一个字符，其他元素要向后移。如果采用从前向后填充，意味着先把其他元素后移，再填充。这就是双层循环。如果双指针来进行后向填充，就会减少一层循环。