5. 替换空格
1. 描述
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
2. 例子
示例 1:
输入：s = “We are happy.”
输出：“We%20are%20happy.”
3. 限制
- 0 <= s 的长度 <= 10000
4. 题解
m 是存在的空格数量，n = m_str.size()
时间复杂度: O(m + n)
空间复杂度: O(m)
因为数组每次中间插入数据都会导致后方数据后移，导致 O(n) 的平均时间开销，而末尾插入则只有 O(1) 的时间开销，因此我们可以预先计算出字符串最终长度，并设置快慢指针不断在最后插入字符。
class Solution
{
public:
// string replaceSpace(string s)
string replaceSpace(string &m_str)
{
int blankCount = 0;
for(auto letter : m_str)
blankCount += (letter == ' ');
m_str += string(blankCount * 2, ' ');
const int oldSize = m_str.size() - blankCount * 2;
const int newSize = m_str.size();
for(int i = oldSize - 1, j = newSize - 1; i >= 0 && j >= 0; i--)
{
if(m_str[i] != ' ')
{
m_str[j] = m_str[i];
j--;
}
else
{
m_str[j] = '0';
m_str[j - 1] = '2';
m_str[j - 2] = '%';
j-= 3;
}
}
return m_str;
}
};