{CareerCup}{每日一题}判断一个字符串中是否有重复的字符

据说每天做一些编程练习题可以防止智商下降，Practice Makes Perfect!

首先是第一题，判断一个字符串中是否有重复的字符。

抛开O(n^2)的暴力遍历方式，假设字符集为ascii编码（solution中特别提示：向面试官说明这一假设很重要！），先得到了一个版本：创建一个int型的数组ascii，并将其元素初始化为0。遍历string，分解得到它的每个字符对应的ascii码值，记为i；ascii[i]++, 若ascii[i]>1，则说明出现了重复字符。代码如下：

bool isUniqueString(string str)
{
    int ascii[256];
    for(int i=0; i<256; i++)
    {
        ascii[i]=0;
    }
    for(int i=0; i<(int)str.length(); i++)
    {
        if((++ascii[(int)str[i]])>1)
            return false;
    }
    return true;
}

看了solution之后，发现自己的解答虽然在思路上和提示相同，但采用的数据结构仍然不够好。其实没有必要开辟int型的数组，只有bool型的就可以了，代码和int型的解答相似，不再赘述。

solution还提供了另一种更加tricky的位操作解决方案，原文假设字符串只包含'a'-'z'之间的字符，在此假设下，只需要一个int型变量checker（32位）就可以起到bool型数组的作用。

在这里给出扩展到了ascii字符集的解答。

bool isUniqueString3(string str)
{
    int char_set[8];
    for(int i=0;i<8;i++)
        char_set[i]=0;
    for(int i=0;i<(int)str.length();i++)
    {
        int index = (int)str[i];
        if(char_set[index/32]&(1<<(index%32)))
            return false;
        char_set[index/32] |= (1<<(index%32));
    }
    return true;
}

两个函数均通过测试。