题目描述

blablabla

样例

blablabla

算法1

(双指针)

这种方法也是剑指offer书上给出的解题方法
blablabla

时间复杂度

O(n)

C++ 代码

class Solution {
public:
    string replaceSpaces(string &str) {
        //面试官在出题的时候重点考察的是算法的时间复杂度和空间复杂度，所以高效是个很好的标准
        //所以第一种方法开辟内存空间面试官会不满意，第二种方法是双指针
        int len = 0;
        for(auto x : str)
        {
            if( x == ' ') len += 3;
            else len++;
        }
        int i = str.size()-1, j = len - 1;
        str.resize(len);
        while(i >= 0)
        {
            if(str[i] == ' ')
            {
                str[j--] = '0';
                str[j--] = '2';
                str[j--] = '%';
            }else
            {
                str[j--] = str[i];
            }
            i--;
        }
        return str;
    }
};