Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4389304
  • 博文数量: 291
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 7924
  • 用 户 组: 普通用户
  • 注册时间: 2016-07-06 14:28
  • 认证徽章:
个人简介

阿里巴巴是个快乐的青年

文章分类

全部博文(291)

文章存档

2018年(21)

2017年(4)

2016年(5)

2015年(17)

2014年(68)

2013年(174)

2012年(2)

分类: 架构设计与优化

2013-05-14 16:50:38

一、判断一个字符串里是否包含了另一个字符串中所有的字符
1、原理
         有两个字符串A和B,每个字符串的字符从A-Z中选取,比如:A="ABCDE",B="ACE",那么A中包含B中所有出现的字符,但如果A="ABCD",则A中不包含B中所有字符。
        “是否包含”问题都可以归结为hashtable或者位图一类的问题,本题可以将A中出现的字符计数存放在长度为26的数组中,比如:array[26]={1, 2, 1, 0,...},然后对B中的字符查找array,对应值不为0则包含该字符,如果扫描完B中所有字符都包含的话就成立,否则不成立。
2、实现
        #include    

        bool AContainB(char *szA, char *szB) 
        {
            if ((NULL == szA) || (NULL == szB))
            {
                return false;
            }

            int array[26] = {0};
            char *temp = szA;
            for (int i=0; *temp++!='\0'; i++)
            {
                array[szA[i]-'A'] += 1;
            }

            temp = szB;
            for (int j=0; *temp++!='\0'; j++)
            {
                if (array[szB[j]-'A'] <=0 )
                {
                    return false;
                }
            }

            return true; 
        }  

        int main()
        {
            char szA[] = "ABCDE";
            char szB[] = "ACE";
            printf("A=%s-->B=%s\n", szA, szB);
            printf("res=%d\n", AContainB(szA, szB));

            return 0;
        }

二、在一个字符串中找到第一个只出现一次的字符
1、原理
         给定一个字符串,比如:A="AECDACBD",那么A中第一个只出现一次的字符是'E'。
        “判定存在”问题都可以归结为hashtable或者位图一类的问题,本题可以先扫描一遍A,将A中出现的字符计数存放在长度为256的数组中,比如:array[256]={1, 2, 1, 0,...},256即ASCII码总数,这样就涵盖了所有字符,然后再次顺序扫描A,找到字符计数为1字符返回即可。
2、实现
        #include    

        int FirstOnlyCharacter(char *szString) 

        {
            if (NULL == szString)
            {
                return -1;
            }

            int array[256] = {0};
            char *temp = szString;
            for (int i=0; *temp++!='\0'; i++)
            {
                array[szString[i]] += 1;
            }

            temp = szString;
            for (int j=0; *temp++!='\0'; j++)
            {
                if (array[szString[j]] == 1)
                {
                    return szString[j];
                }
            }

            return -1;  
        }  

        int main()
        {
            char szString[] = "AECDACBD";
            printf("str=%s-->firstonlychar=%c\n", szString, FirstOnlyCharacter(szString));

            return 0;
        }





阅读(2276) | 评论(1) | 转发(1) |
1

上一篇:字符串之压缩

下一篇:字符串之旋转

给主人留下些什么吧!~~

scq2099yt2013-05-14 16:50:53

文明上网,理性发言...

评论热议
请登录后评论。

登录 注册