【OJ】字符串去重并提取出重复字符

2018-02-05 20:23:45来源:cnblogs.com作者:notfound945人点击

分享

  ACM上一道简单的字符串题,从网上找了下类似的代码进行参考外加之个人思考,想到此好思路。

题目大意

    任意输入一行字符串,检索重复出现的字符。将原字符串中的重复字符删除后按照原顺序输出,同时按照原顺序输出有哪些字符是重复的。
输入

输出

  两个输出之间空一行    
样例输入

    ads_fagaerididfhdus_afiew
样例输出

    ads_fgerihuw    ads_fei

   看到此题,第一想法就是用个初始值全为 0 的flag[100000]数组来进行标记,首先是遍历整个字符串,从第i个字符开始与整个字符串所有字符(就不单独把第 i 个字符除开,后面计算时可能有点麻烦,进行判断时 flag[i] == 1 就行了)进行一一比较,如有重复则flag[i] ++ ,最后通过 flag[i] 的值来判断。如果 falg[i] == 1 则打印到屏幕上,但是这样只是把没有重复的字符打印出来,并没有将重复的字符删除而且重复的字符都没有打印到屏幕上,这样明显是不符合题目要求。

  那要怎样呢?是遍历字符串时把第 i 个字符与字符前或字符后的字符进行对比么,如果这样可以根据各个重复字符的 flag[i] 进行判断,到时只需把 flag[i] == 0 和 flag[i] == 2 打印到屏幕上就可以了。这个对题目中的第一要求删除重复字符按顺序打印到屏幕还过得去,不过第二个按照顺序提取重复的字符又怎么做?因为重复字符出现可不一定是两次,这样 flag[i] 可能为 1、2、3、、4、、、 这样就不要判断了。

  通过参考网上的代码,那么这个思路就出来了。众所周知,我们键盘输入的字符在ASCII字符集都有对应的ASCII码,把字符的ASCII码一一对应,可以看成一个容量为 128 的数组,字符ASCII的编码就在 0-127 之间嘛。此思路也解决前面那种每个位置上的字符都要一个 flag 空间了,只需要 128 容量的空间就足矣。

  在这条思路下,我们就初始化所有 flag[128] = {} 在遍历字符串时先判断 flag[str[i]] 是否为 0 因为初始都是 0 所以每个字符对应的 ASCII 码的 flag 都是为 0 的,而在每个进行了判断且满足条件的 flag[str[i]] 都改变其值为 1 (不为0即可),这样当下一个相同字符进行判断时就不满足条件被拒之门外,而所有满足条件的都打印到屏幕上了。这样子题目的第一要求就满足了,

  那么第二要求呢?还是这个套路,有点像是递归的味道。就之前的判断进行下去,如果进行 str[i] 被拒之门外了怎么办呢?我们还要打印它一次呢,还有它们了中也是有重复的呀。OK , 旧套路嘛 将上边不满足条件的 flag[str[i]] = 2 (不为 1 就行 为了区分就赋值为 3 吧)。

  好,这样之后,所有重复的字符ASCII码对应的 flag[str[i]] 的值都为 2 了,就像第一要求那样所有字符对ASCII对应的 flag[str[i]] 都为 0,同样就可以套用第一要求的代码模型啦。再来一个for循环,以 flag[str[i]] == 2 作为判断条件,如果满足条件则将其改变为 3 (不为 2 就行)。这时不满足条件的就不管了,因为已达到要求 那些就没用了,我们将满足条件的打印到屏幕上就行了。

  最后,代码如下:

#include<stdio.h>#include<string.h>int main(void){    int i;    char a[100000];    int flag[128] = {};    gets(a);    for(i = 0; i < strlen(a); i ++)        if(flag[(int)a[i]] == 0)        {            flag[(int)a[i]] = 1;            printf("%c", a[i]);        }//删除重复字符后按照原顺序打印          else            flag[(int)a[i]] = 2;
printf("/n/n");//空一行 for(i = 0; i < strlen(a); i ++) if(flag[(int)a[i]] == 2) { flag[(int)a[i]] = 3; printf("%c", a[i]); }//按照原顺序打印重复字符}

相关文章

    无相关信息

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台