【Leetcode字符串-双指针】剑指 Offer 05. 替换空格（填充类题目好的解法！！）

• 剑指Offer-05
• • 1.问题描述
  • 2.解决方案
  • • 解法一：从前往后遍历
    • 解法二：扩容加从后往前遍历双指针
    • • 算法优点：
      • 代码实现：

不用多说，思路很清晰，就是从前往后遍历，遇到空格，就整体后移然后填充"%20"，但是时间复杂度就是O(n^2)，因为每次添加元素都要将添加元素之后的所有元素向后移动，代码这里就不给出了！

其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
1.把这道题目做到极致，就不要只用额外的辅助空间了！首先扩充数组到每个空格替换成"%20"之后的大小。
2.然后从后向前替换空格，也就是双指针法，i指向新长度的末尾，j指向旧长度的末尾。
3.不用申请新数组。
4.从后向前填充元素，避免了从前先后填充元素要来的，每次添加元素都要将添加元素之后的所有元素向后移动，时间复杂度将为o(n)

先统计再扩充，扩充用到了resize()，然后从后往前填充！

class Solution {
public:
    string replaceSpace(string s) {
        //统计空格字符的数量
        int oldSize=s.size();
        int count=0;
        for (auto item: s) {
            if(item==' ') count++;
        }

        //扩充
        s.resize(s.size()+count*2);
        int newSize=s.size();

        //从后先前将空格替换为"%20"
        //...j(oldSize-1)...i(newSize-1)
        //j