剑指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; }
编辑:孙小北
本文地址: https://www.xiaowangyun.com/wyblog/detail/?id=176
版权归属: www.xiaowangyun.com 转载时请以链接形式注明出处
0 条评论