算法1
(线性扫描) $O(n)$
这个题在C++里比较好做，我们可以从前往后枚举原字符串：
- 如果遇到空格，则在string类型的答案中添加
"%20"； - 如果遇到其他字符，则直接将它添加在答案中；
但在C语言中，我们没有string这种好用的模板，需要自己malloc出char数组来存储答案。
此时我们就需要分成三步来做：
- 遍历一遍原字符串，计算出答案的最终长度；
- malloc出该长度的char数组；
- 再遍历一遍原字符串，计算出最终的答案数组；
时间复杂度分析
原字符串只会被遍历常数次，所以总时间复杂度是 $O(n)$。
C++ 代码
class Solution {
public:
string replaceSpaces(string &str) {
string res;
for (auto x : str)
if (x == ' ')
res += "%20";
else
res += x;
return res;
}
};
算法2
(双指针扫描) $O(n)$
在部分编程语言中，我们可以动态地将原数组长度扩大，此时我们就可以使用双指针算法，来降低空间的使用：
- 首先遍历一遍原数组，求出最终答案的长度length；
- 将原数组resize成length大小；
- 使用两个指针，指针
i指向原字符串的末尾，指针j指向length的位置； - 两个指针分别从后往前遍历，如果
str[i] == ' '，则指针j的位置上依次填充'0', '2', '%'，这样倒着看就是"%20"；如果str[i] != ' '，则指针j的位置上填充该字符即可。
由于i之前的字符串，在变换之后，长度一定不小于原字符串，所以遍历过程中一定有i <= j，这样可以保证str[j]不会覆盖还未遍历过的str[i]，从而答案是正确的。
时间复杂度分析
原字符串只会被遍历常数次，所以总时间复杂度是 $O(n)$。
C++ 代码
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;
}
};
练习STL
棒
秒
srt.find（查找函数）
sring::nops表示size_t的最大值（Maximum value for size_t）。该值表示“直到字符串结尾”，
srt.replace替换函数
size_t 类型表示C中任何对象所能达到的最大长度，它是无符号整数。
t 起始位置
1 长度
“%20” 新长度
C++的方法为什么不能直接对str来操作，而是又加了一个变量res
str每个元素大小是1字节，不能插入”%20”
可以使用replace函数
class Solution {
public:
string replaceSpaces(string &str) {
for (int i = 0; i < str.size(); i ++){
if (str[i] == ‘ ‘) cout << “%20”;
else cout << str[i];
}
}
};
好奇怪这样写会RE，输出没问题
这个函数返回类型是string，这样写没有返回值的
明白了 谢谢你~
auto 是在哪里讲的来自？
auto,可自动推导类型的C++保留字。
妙
为什么j要倒着循环，正着可以吗？有hxd试了吗？
懂了，倒着输出i，j是一直大于i的，所以这就保证了j不回去遮盖住i没有遍历到的值。如果正着输出j会遮盖住i
灿哥这种解法开辟额外空间了啊，感觉面试官会不会不满意，用指针怎么解呀
刚刚在上面添加了算法2——双指针算法，可以参考一下hh
妙得我想留下评论！！！ 这个j – 用的完美~
把StringBuffer转换成String类型,采用replace()
class Solution {
public String replaceSpaces(StringBuffer str) {
String str1=str.toString();
return str1.replace(” “,”%20”);
}
}
class Solution {
public:
string replaceSpaces(string &str) {
int start = 0;
int end=str.length();
string result;
for(int i=0;i<end;i++)
{
if(str[i]==’ ‘)
{
result+=”%20”;
}
else
{
result+=str[i];
}
}
return result;
}
};怎么样
利用字符串重载有啥缺点吗？
class Solution {
public:
string replaceSpaces(string &str) {
string s;
for(auto x : str){
if(x == ‘ ‘) s += “%20”;
else s += x;
}
return s;
}
};
蹲蹲大佬解答 我看着感觉简单易懂
str.resize(len)是一个字符串操作函数，它用于改变字符串的长度。具体来说，它会将字符串str的长度调整为len指定的长度。
如果len小于当前字符串的长度，那么str会被截断为len长度，多余的部分会被删除。
如果len大于当前字符串的长度，那么str会被扩展为len长度，多出的部分会用空字符填充。
Y总YYDS；
其实c的函数也能解决得很好
其实c的函数也能解决得很好
用c++怎么写，CE了
为什么新定义的st如果不初始化就会报错，定义之后就能通过？
难道字符串不初始化不是默认字符串长度可变么？
string里面没东西不能像数组那样操作他吧
女少口阿yxc!
我记得有一个sstring，如果不严格要求是不是可以拿那个写