文章目录
同步GitHub在此 👉 https://github.com/TeFuirnever/GXL-Skill-Tree
- 剑指 Offer（C++版本）系列：总目录和一些提高效率的说明
- 剑指 Offer（C++版本）系列：剑指 Offer 03 数组中重复的数字
- 剑指 Offer（C++版本）系列：剑指 Offer 04 二维数组中的查找
- 剑指 Offer（C++版本）系列：剑指 Offer 05 替换空格
1、题干
替换空格
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
限制：
0 <= s 的长度 <= 10000
通过次数227,105提交次数297,856
2、遍历添加
最应该想到的方法是，首先新建一个字符串，然后从头遍历原字符串，如果遇到满足要求的，修改即可，如果没遇到，保留下来。
算法流程：
- 初始化一个字符串，记为 res ；
- 遍历原字符串 s 中的每个字符 x ：
- 当 x 为空格时：向 res 后添加字符串 “%20” ；
- 当 x 不为空格时：向 res 后添加字符 x ；
- 返回字符串 res 。
//面试题05.替换空格
class Solution {
public:
string replaceSpace(string s) {
string res;
for (auto x : s)
{
if (x == ' ') res += "%20";
else res += x;
}
return res;
}
};
/*
时间复杂度：O(n)。遍历字符串 s 一遍。
空间复杂度：O(n)
*/
3、原地修改
需要注意的是，空间复杂度，由于新建一个答案字符串，所以空间复杂度不是常数。
算法流程：
- 初始化：原字符串 s 的长度 oldl ；
- 统计空格数量：遍历 s ，遇空格则 s += “00”；
- 重新初始化：原字符串 s 长度 newl ：添加完 “%20” 后的字符串长度；
- 倒序遍历修改：i 指向字符串 s 尾部元素；
- 当 s[i] 为空格时：将字符串 newl 的元素分别修改为 “%20” ，每次修改后都需要移动 newl ；
- 当 s[i] 不为空格时：将字符串 newl 的元素修改为 c ；
- 返回已修改的字符串 s ；
//面试题05.替换空格
//标准做法
class Solution {
public:
string replaceSpace(string s) {
int oldl = s.length() - 1;
for (int i = 0; i <= oldl; i++) {
if (s[i] == ' ') {
s += "00";
}
}
int newl = s.length() - 1;
if (newl <= oldl) {
return s;
}
for (int i = oldl; i >= 0; i--) {
char c = s[i];
if (c == ' ') {
s[newl--] = '0';
s[newl--] = '2';
s[newl--] = '%';
}
else {
s[newl--] = c;
}
}
return s;
}
};
4、复杂度
/*
时间复杂度：O(n)。遍历字符串 s 一遍。
空间复杂度：O(1)。由于是原地扩展 s 长度，因此使用 O(1)O(1) 额外空间。
*/
——————————————————————————————————————
- 剑指 Offer（C++版本）系列：总目录和一些提高效率的说明
- 剑指 Offer（C++版本）系列：剑指 Offer 03 数组中重复的数字
- 剑指 Offer（C++版本）系列：剑指 Offer 04 二维数组中的查找
- 剑指 Offer（C++版本）系列：剑指 Offer 05 替换空格
—————————————————————————————————————
本文由 leetcode、牛客、公众哈哦、知乎共同支持！
https://leetcode-cn.com/u/tefuirnever/
https://blog.nowcoder.net/wsguanxl
https://mp.weixin.qq.com/s/bDwxwQfZytIx4mAn8eK20Q
