题解 | #替换空格#

题解一:暴力(原字符串上修改)
题解思路:从头开始遍历数组，当遇到空格，先将后续字符往后移2个位置，再在空格位置以及后两个位置填上"%20"这三个字符
时间复杂度：O(n^2)，暴力的两次循环，第一层循环找空格位置，第二层循环将空格后面的字符往后移2位置
空间复杂度：O(1)，只使用常数个临时变量存放中间值

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;
    }
};

题解二：遍历字符串,拼接(利用一个新字符串)
题解思路： 从头开始遍历字符串，当遇到空格，则temps+="%20"，否则temps+=s[i];
时间复杂度：O(N)，遍历了一次字符串，找其中的空格数
空间复杂度：O(N)，使用了一个s1的字符串保存修改后的结果

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string replaceSpace(string s) {
        // write code here
        string temps;
        for(int i = 0 ; i < s.size(); i++ )
        {
            if (s[i] == ' ')
                temps += "%20";
            else 
                temps += s[i];
        }
        return temps;
    }
};

题解三：原地修改（双指针）
题解思路：
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];
复杂度分析：
时间复杂度：O(N)，遍历一次字符串，找其中的空格位置
空间复杂度：O(1)，只使用常数个临时变量存放中间值

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;
      }
};