题解 | #替换空格#

题解一:暴力(原字符串上修改)
题解思路:从头开始遍历数组，当遇到空格，先将后续字符往后移2个位置，再在空格位置以及后两个位置填上"%20"这三个字符

示例：

复杂度分析：
时间复杂度：，暴力的两次循环，第一层循环找空格位置，第二层循环将空格后面的字符往后移2位置
空间复杂度：，只使用常数个临时变量存放中间值

实现如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string replaceSpace(string s) {
        // write code here
        int result=0;
        for(auto i:s){
            if(i==' ')++result;
        }
        int l=s.size();
        s.resize(l+result*2);
        for(int i=0;i<s.size();){
            if(s[i]==' '){//字符为空格
                for(int j=s.size()-1;j>i+2;j--){//i字符之后字符整体后移2个位置
                    s[j]=s[j-2];
                }
                s[i]='%';//填充为%20
                s[i+1]='2';
                s[i+2]='0';
            }else{
                i++;
            }
        }
        return s;
    }
};

题解二：遍历字符串,拼接(利用一个新字符串)
题解思路： 从头开始遍历字符串，当遇到空格，则s1 +="%20"，否则s1+=s[i];
示例：

复杂度分析：
时间复杂度：，遍历了一次字符串，找其中的空格数
空间复杂度：，使用了一个s1的字符串保存修改后的结果

实现如下：

class Solution {
public:
    string replaceSpace(string s) {
        // write code here
        string s1="";
        for(int i = 0;i<s.length();i++)
        {
            if(s[i]!=' ') s1+= s[i];
            else s1+="%20";
        }
        return s1;

    }
};

题解二：原地修改（双指针）
题解思路：
1.统计字符串中空格的个数num,接着在原字符串尾增加长度size=num*2.
2.使用 i 指向扩展前字符串尾部字符，j 指向扩展之后的字符串末尾位置。
3、开始遍历字符串
a.当s[i]为空格，在s[j]='0',s[j-1]='2',s[j-2]='%';
b.当s[i]为字符，s[j]=s[i];
示例：

复杂度分析：
时间复杂度：，遍历一次字符串，找其中的空格位置
空间复杂度：，只使用常数个临时变量存放中间值

class Solution {public:    string replaceSpace(string s) {
        int num = 0,length = s.length();
      for(auto i : s)
      {
          if(i==' ') num++;//统计空格数
      }
      s.resize(length + 2*num);//拓展长度
      for(int i = length-1,j = s.size()-1; j>i;j--,i--)
      {
          if(s[i]!=' ') s[j] = s[i];//当s[i]为字符，s[j]=s[i];
          else//为空格，补上%20;
          {
              s[j] = '0';
              s[j-1] = '2';
              s[j-2] = '%';
              j-=2;
          }
      }
      return s;
      }
};