剑指 Offer 05. 替换空格（字符串 双指针法）(Leetcode刷题笔记)
欢迎大家访问我的GitHub博客
https://lunan0320.cn
文章目录
题目
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = “We are happy.”
输出：“We%20are%20happy.”
解题代码 C++
解题思路： 先计算空格数，然后resize（）方法为其重新分配字符串的长度。
接着用两个指针去依次替换。
class Solution {
public:
string replaceSpace(string s) {
int length1 = s.size();
int count = 0;
// 先判断有多少的空格
for (int i = 0; i < length1; i++){
if (s[i] == ' '){
count++;
}
}
//为字符串重新划分大小
s.resize(s.size() + 2 * count );
int length2 = s.size();
int i = length2 - 1;
int j = length1 - 1;
//注意此处的条件
while(i >= 0 && j >= 0){
//不是空格的话直接替换
if (s[j] != ' '){
s[i] = s[j];
i--;
j--;
}else{
//遇到空格就替换成%20
s[i] = '0';
s[i-1]='2';
s[i-2]='%';
i -= 3;
j--;
}
}
return s;
}
};
算法效率
时间复杂度O(n)
空间复杂度O(1）
执行用时： 0 ms , 在所有 C++ 提交中击败了100.00% 的用户
内存消耗：6.1 MB , 在所有 C++ 提交中击败了 47.56% 的用户