每日一题11:替换字符串中的空格

用指定的字符或字符串替换某个字符串中出现的所有空格,当用字符替换字符是,自然是很简单的,但是当使用字符串替换字符时,如果还是从前往后遍历,遇到指定字符就将其后所有字符往后移出足够空间的话,当字符串中的空格很多时,反复的移动字符会带来性能上的损失。但是如果是从后往前遍历呢?可以先遍历一次原字符串,得到字符串中空格的个数,然后就可以计算出实际需要的空间,再假设原字符串所在缓冲区有足够空间(否则新建一个缓冲区从前往后遍历就行了,这里说的是在不新建缓冲区的情况下做这件事),,那么就可以计算出每个字符最后的位置,到算法中可以用一个指针q指向替换后字符串的最后一个字符(也就是字符串结束符)所在的位置,指针p指向原字符串的最后一个字符(字符串结束符),然后两个指针向前遍历,如果p指向的字符为空格,那么就将替换字符串从后向前填充到q指向的位置(该过程中p不动,q继续向前,第一次遍历后所做的计算保证q不会追上p),然后两个指针继续向前遍历。这样就得到一个O(N)的算法了。

;const int bufsize = 1024;void Replace(char** str, char target_char,const char* replace_str){int replace_str_len = strlen(replace_str);char* p = *str;int target_char_fre = 0;int str_len = 0;while(*p){if(*p == target_char) ++target_char_fre;++str_len;++p;}int extend_count = target_char_fre * (replace_str_len – 1);char * q = p + extend_count;int j = 0;while(j <= str_len){if(*p != target_char)*q– = *p–;else{const char* r = &replace_str[replace_str_len – 1];int i = 0;while(i < replace_str_len){*q– = *r–;++i;}–p;}++j;}}int _tmain(int argc, _TCHAR* argv[]){char * str = new char[bufsize];strcpy(str,” wo shi zhong guo ren!”);Replace(&str,’ ‘,”%20″);cout<<str<<endl;return 0;}

如果从一个方向走不通,那就换个方向试试!这种方法还可以用于数组的插入等类似的情景中。

感受不同地域不一样的节奏与表象。

每日一题11:替换字符串中的空格

相关文章:

你感兴趣的文章:

标签云: