2018-03-16 孙小北

剑指Offer面试题(四)空格替换

剑指Offer面试题(四)空格替换

题目:设计一种方法,将一个字符串中的所有空格替换成 %20 。你可以假设该字符串有足够的空间来加入新的字符,且你得到的是“真实的”字符长度。

你的程序还需要返回被替换后的字符串的长度。(挑战:在原字符串(字符数组)中完成替换,不适用额外空间)

样例:对于字符串"Mr John Smith", 长度为 13,替换空格之后,参数中的字符串需要变为"Mr%20John%20Smith",并且把新长度 17 作为结果返回。

分析:

常规解法是,从头到尾遍历,遇到空格时,把空格后面的字符串依次后移。但该种方法会导致某些字符重复移动,时间复杂度较高约为O(n2)。
    推荐解法:先计算出原字符串中有多少空格,然后从尾到头遍历,因为一开始就知道被移动字符的最终位置,因此可以避免字符的重复移动。时间复杂度O(n):

1.首先计算字符串中空格的个数。每个空格用三个字符替换,那么每多一个空格那么替换后的字符串将多出来两个字符。因此计算出替换后字符串的长度。

2.在字符串中设置两个索引,p1索引指向字符串的结尾即'\0'处,另外一个指向计算出的替换后字符串长度的位置。

3.当未遇到空格时候,将p1所指的字符赋值为p2所指的字符。同时索引p1,p2均向前移动一个位置

4,当索引p1遇到空格时候将p2,p2-1,p2-2,这三个位置分别替换为'%' '2' '0',然后索引p1向前移动一个位置,p2向前移动三个位置。

5.替换的结束条件是,当p1和p2索引位置相同时,这时候替换空格结束。

int replaceBlank(char string[], int length) { 
    //先统计空格个数,然后替换
    //注意char类型用'''  
    //注意判空 
    if(string == NULL && length <= 0)
        return 0; 
    int spaceNum=0;
    int i=0;
    while(string[i] != '\0'){ 
        if(string[i]==' ') 
            spaceNum++; 
        i++;
    }
    //新字符串的长度
    int newlength=length+2*spaceNum;
    int j=newlength-1;//从最后一位开始判断,若出现空格,将替换为20%
    while(j>=0){ 
        if(string[length-1]==' '){ 
            string[j--]='0';
            string[j--]='2'; 
            string[j--]='%';
        }else{
            string[j--]=string[length-1];
        }
        length--;
    } 
    return newlength;
}




编辑:孙小北

本文地址: http://www.xiaowangyun.com/wyblog/detail/?id=176

版权归属: www.xiaowangyun.com   转载时请以链接形式注明出处

物以类聚

最新评论

2017-10-06

一辈子不长,只有珍惜了,才不至于后悔。

2017-10-06

懂得感恩,才能走得更远。

标签云

归档

取消

感谢您的支持,您的每一次打赏都是一次鼓励!

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦