转载

常见面试题系列1——原地消除字符串连续的空白字符

前两天看到一个文章 “ 白板编程浅谈——Why, What, How ” 里说“原地消除字符串的重复空白(例:"ab   c  d e" => "ab c d e")则是一道合格的题目,因为即便不使用库函数,合格的面试者也能够在 20 分钟内完成这道题目。” 就试着自己写了下这个功能的实现。

思路:因为题目限制了是原地,而不能借助一个辅助临时数组。所以第一想法可能会想到,从前往后遍历,遇到连续空白就将后面的内容全部向前移动,这样的确可以很快的写出来,但是时间复杂度就比较大了(0(n^2))。所以就想到用两个游动指针来标记已经遍历到的当前位置pRight和删除空白后当前位置pLeft。

一、首先呢,我考虑写一个删除字符串中所有空格(当然特定其他字符也是一样的),就写了下面的代码:

常见面试题系列1——原地消除字符串连续的空白字符
 1 //删除字符数组str中的所有某个特定字符del  2 char * delChar(char* str, char del = ' ')  3 {  4     //防止传入无效参数-空指针  5     if(str==0 || *str==0 || del==0)  6         return str;  7     char *pLeft=str, *pRight=str;  8     while(*pRight!=0 && *pRight!=del)  9         ++pRight; 10     pLeft = pRight;//第一个要删的位置 11     while(*pRight==del) //跳过要删除的元素 12         ++pRight; 13     //当前pRight指向第一个要向前移动的元素 14     for(;*pRight!=0;++pRight) { 15         //*pRight不需要删除则向前复制元素 16         if(*pRight!=del) { 17             *pLeft = *pRight; 18             ++pLeft; 19         } 20     } 21     *pLeft = 0; 22     return str; 23 }
View Code

也可以这样:

常见面试题系列1——原地消除字符串连续的空白字符
 1 //删除字符数组str中的所有某个特定字符del  2 char * delChar2(char* str, char del = ' ')  3 {  4     //防止传入无效参数-空指针  5     if(str==0 || *str==0 || del==0)  6         return str;  7     char *pLeft=str, *pRight=str;  8     //一直遍历到字符串尾部  9     for(;*pRight!=0;++pRight) { 10         //*pRight到达第一个不需要删除的元素 11         if(*pRight!=del) { 12             //不指向同一元素 13             if(pLeft!=pRight) 14                 *pLeft = *pRight; 15             ++pLeft; 16         } 17     } 18     //最后一位置0,不执行这一步将会有多余的上次残留输出 19     *pLeft = 0; 20     return str; 21 }
View Code

二、然后,删除连续特定字符总体来说和上面代码的框架差不多,也是用两个游动指针来指向已经遍历的位置pRight(跑的比较快,所以在右边)和删除连续字符后的当前位置pLeft(跑的比较慢),只不过是要多加一层判断,连续两个要删除的字符出现时才让pRight跑得比pLeft快。代码如下:

常见面试题系列1——原地消除字符串连续的空白字符
 1 //删除字符数组str中的所有连续重复的某个特定字符del  2 char * delRepeatedChar(char* str, char del = ' ')  3 {  4     //防止传入无效参数-空指针  5     if(str==0 || *str==0 || del==0)  6         return str;  7     char *pLeft=str, *pRight=str;  8     while(*pRight!=0 && *pRight!=del)  9         ++pRight; 10     pLeft = pRight;//第一个 所指元素是要删除的字符 11     for(; *pRight!=0; ++pLeft, ++pRight) { 12         //pRight所指元素是要删除的字符 13         if(*pRight==del) { 14             //下一个元素也是要删除的字符,则删除下一个字符 15             if(*(pRight+1)==del){ 16                 *pLeft++ = *pRight; 17                 //移动到当前需要向前复制的位置 18                 while(*pRight==del) 19                     ++pRight; 20                 //复制元素 21                 *pLeft = *pRight; 22                 continue; 23             } 24         } 25         //复制元素 26         *pLeft = *pRight; 27     } 28     //最后一位置0,否则尾部可能有上一次的残留字符 29     *pLeft = 0; 30     return str; 31 }
View Code

至此,这个功能的代码算是写完了,来弄一个主函数,调用一下吧:

#include<stdio.h> char * delRepeatedChar(char* str, char del); int main() {  char str[128] = "   a c b  cccd f  ghh jk lmnnn qr  st ";  char del = 'c';  printf("请输入一个源字符串:");  while(gets(str)) { //一定要用gets而不是scanf,因为可能包含空格   printf("请输入一个要删除的字符:");   del = getchar();   printf("<%s> 删除连续的字符'%c'后:/n",str,del);   printf("<%s>/n/n请输入一个源字符串:",delRepeatedChar(str,del));   getchar();  }  return 0; } 
正文到此结束
Loading...