给定一个字符串str和一个子串SubStr,如果str里面的空间足够,写一个函数将str里面的字符ch替换成SubStr。书中只是一个特例:将空格替换成%20.
题目分析:
如果从前到后扫描str,碰到一个ch,那么ch后面的所有字符都要向后挪SubLen-1个位置。这样做的效率肯定是不高的,怎么在O(n)的时间复杂度内完成这个操作呢。从前到后扫描不行,那就从后到前扫描。如果预先知道了有多少个字符需要替换,是不是就能预先之后替换之后str的长度,也就是最后一个字符的位置,那就从最后一个字符开始存呗。步骤:
*扫描str,确定ch的个数为cnt。
*计算新str的大小,为cnt*(SubLen-1)+StrLen
*从后到前扫描,遇到ch,从后到前复制SubStr
代码如下:
//得到指定字符的数量 int GetSpaceCount(char *str, int nLen, char ch) { if(!str || nLen < 1) return -1; int cnt = 0; for(int i = 0; i < nLen; ++i) { if(str[i] == ch) ++cnt; } return cnt; } //将指定字符换成指定字符串 void Replace(char *SrcStr, char *DesStr, char ch) { if(!SrcStr || !DesStr) return; int SrcLen = strlen(SrcStr); int DesLen = strlen(DesStr); int cnt = GetSpaceCount(SrcStr, SrcLen, ch); int i,k; k = cnt * (DesLen - 1) + SrcLen;//如果有必要需要检查够不够放 SrcStr[k]= '\0'; for(i = SrcLen - 1; i >= 0; --i) { if(SrcStr[i] == ch) { for(int j = DesLen - 1; j >=0; --j) SrcStr[--k] = DesStr[j]; } else SrcStr[--k] = SrcStr[i]; } } int main() { char Str[100]; char SubStr[10]; char ch; while(gets(Str) && gets(SubStr)) { scanf("%c", &ch); getchar(); Replace(Str, SubStr, ch); puts(Str); } }
相关题目链接:单词反转。参考另外一篇博客http://blog.csdn.net/kay_zhyu/article/details/8769026。其实有些题很简单,但是怎么样把代码写得漂亮,那就需要本事了。