【OJ】字符串去重并并按原顺序打印出重复字符

2018-06-18 03:53:35来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

  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]); }//按照原顺序打印重复字符 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C语言的函数调用过程(栈帧的创建与销毁)

下一篇:c++(002)学习输入cin