剑指offer-替换空格

佚名 5年前 (2019-01-31) 算法 1126人围观抢沙发百度已收录

剑指offer中的第二题替换空格的写法，以下给出Python、C++的写法。

Python写法

运行时长约30 ms

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        newstr=s.replace(' ','%20')
        return newstr

C++写法

class Solution {
public:
    void replaceSpace(char *str,int length) {
        for(int i = 0; i<length ; i++){
            if(str[i]==' '){//如果存在空格
                //then replace
                for(int j = length+1;j>=i+3;j--){//把后面的往后移动两个单位
                    str[j]=str[j-2];
                }
                str[i]='%';
                str[i+1]='2';
                str[i+2]='0';
                length+=2;
            }
        }
    }
};

运行时长约7 ms，但是还可以优化。上述的方式是将字符串从前往后遍历的，如果从后往前遍历的话将更节省时间，因为从前往后遍历，每遇到一个空格需要将后面所有字符后移两个单位，但是如果提前将要往后移动的空格数量统计出来然后从后往前遍历，那么每次移动只需要动空格与空格之间的内容了，避免了多次移动。

class Solution {
public:
    void replaceSpace(char *str,int length) {
        if(str==NULL||length<0)
            return ;
        int i=0;
        int oldnumber=0;//记录以前的长度
        int replacenumber=0;//记录空格的数量
        while(str[i]!='\0')
            {
               oldnumber++;
               if(str[i]==' ')
                   {
                     replacenumber++;
                   }
                  i++; 
            }
        int newlength=oldnumber+replacenumber*2;//插入后的长度
        if(newlength>length)//如果计算后的长度大于总长度就无法插入
            return ;
        int pOldlength=oldnumber; //注意不要减一因为隐藏个‘\0’也要算里
        int pNewlength=newlength;
        while(pOldlength>=0&&pNewlength>pOldlength)//放字符
            {
              if(str[pOldlength]==' ') //碰到空格就替换
                  {
                     str[pNewlength--]='0';
                     str[pNewlength--]='2';
                     str[pNewlength--]='%';
                  }
             else //不是空格就把pOldlength指向的字符装入pNewlength指向的位置
               {
                    str[pNewlength--]=str[pOldlength];
               }
             pOldlength--; //不管是if还是elsr都要把pOldlength前移
           }
    }
    
};

经过优化，运行时长约为 4 ms。

Java写法

public class Solution {
    public String replaceSpace(StringBuffer str) {
        if(str==null)return null;
        return str.toString().replaceAll(" ","%20");
    }
}