首页 > 代码库 > 字符串替换空格
字符串替换空格
题目:请实现一个函数,把字符串中的每个空格替换成"%20",并尽可能的降低时间复杂度。例如:输入"We are happy.",则输出"We%20are%20happy."
分析:最直接的做法就是从头到尾扫描字符串,每一次碰到空格字符的时候就做替换。但是这样是把一个字符替换成3个字符,我们必须要把空格后面的所有的字符都后移两个字节,否则就会有两个字符别覆盖,其时间复杂度为O(n2)
我们可以先遍历一次字符串,统计出字符串中空格的总数,从而计算出替换后字符串的总长度。然后我们从字符串的尾部进行复制替换。设置两个指针P1,P2,P1指向原字符串长度的结尾,P2指向替换后字符串的结尾,然后向前移动P1,逐个P1所指的复制到P2,当遇到空格时,将P1向前移动一格,然后在P2之前插入"%20",然后将P2前移三个字符串,然后继续前进,最终完成。这种算法的时间复杂度是O(n),其C++代码如下:
void ReplaceBlank(cahr string[].int length) { if(string==NULL||length<=0) return; int originalLength=0; int numberOfBlank=0; int i=0; while(string[i]!=‘\0‘) { ++originalLength; if(string[i]==‘ ‘) ++numberOfBlank; ++i; } int newLength=originalLength+numberOfBlank*2; if(newLength>length) return; int indexOfOriginal=originalLength; int indexOfNew=newLength; while(indexOfOriginal>=0&&indexOfNew>indexOfOriginal) { if(string[indexOfOriginal]==‘ ‘) { string[indexOfNew--]==‘0‘; string[indexOfNew--]==‘2‘; string[indexOfNew--]==‘%‘; } else { string[indexOfNew--]=string[indexOfOriginnal]; } indexOfOriginnal; } }
本文出自 “仙路千叠惊尘梦” 博客,请务必保留此出处http://secondscript.blog.51cto.com/9370042/1581314
字符串替换空格
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。