题目描述
请实现一个函数，把字符串中的每个空格替换成
"%20"。数据范围
0≤ 输入字符串的长度 ≤1000。
注意输出字符串的长度可能大于 1000。
样例
输入："We are happy." 输出："We%20are%20happy."
方法一：STL O(n)
我们可以利用 c++ 中 string 自带的函数 find 和 replace 解决该题，注意使用规范：
find函数的返回值是整数，假如字符串存在包含关系，其返回值必定不等于npos ，而是返回查找的字符串在该字符串中出现的下标。但如果字符串不存在包含关系，那么返回值一定是 npos 。所以这里要用一个 size_t 类型的变量来接收返回值。
replace 函数的一个参数代表要开始替换的下标位置，第二个参数代表要替换字符串中多少个字符，第三个参数是要替换进去的字符串。
class Solution { public: string replaceSpaces(string& str) { size_t t; while ((t = str.find(' ')) != string::npos) { str.replace(t, 1, "%20"); } return str; } };
方法二：线性扫描 O(n)
另外开一个字符串数组用于存储答案，然后从头往后遍历 str ，如果遇到空格就换成 "%20" 加到 res 中即可。
class Solution { public: string replaceSpaces(string& str) { string res = ""; for (auto x : str) { if (x == ' ') res += "%20"; else res += x; } return res; } };
方法三：双指针 O(n)
我们可以优化一下空间复杂度，直接在原数组中进行修改：
第一步： 先遍历数组计算最终需要多少个字，如果是空格长度就加 3 ，因为最终一个空格要替换成三个字符；如果是其它字符，就正常加 1 。
第二步： 对 str 进行 resize ，重新定义字符串数组的长度。
第三步： 从后前遍历，如果不是空格，就将 i 处的字符移到 j 处；如果是空格，则将空格当做三个字符进行替换，这里要注意的是要按照 02% 赋值，这样正序输出时才是 %20 。
class Solution { public: string replaceSpaces(string& str) { //先计算最终数组的长度 int len = 0; for (auto x : str) if (x == ' ') 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; } };
欢迎大家在评论区交流~
