algorithm - 检查字符串中的重复字符

Question

在一次采访中，我被要求检查给定字符串是否有重复字符。通过谷歌搜索这个问题，我了解到一个使用位操作的问题。

bool check(char*name)
{
     int i;
     int checker=0;
     for(i=0;name[i]!=0;i++)
     {
        int val=name[i]-'a';
        if((checker&(1<<val))>0)return false;
          checker|=(1<<val);
     }
     return true;
 }

我检查了这段代码，它工作正常。但我不明白这行代码背后的逻辑。

> if((checker&(1<<val))>0)return false;
>               checker|=(1<<val);

第二个疑问是，如果字符串太长或包含 Unicode(2 字节宽的字符)，这是否可行？

Answer 1

该算法使用每个 ascii 字符 1 位来指示集合的存在。所以它至少适用于英文小写字母——其中 26 个字母和连续的 ascii 代码。a= 000001，b= 000010，c= 000100，等等。'aacaaccc' 和 'ac' 和 'ca' 都将编码为 000101，而不管 a 和 c 出现的次数。因此字符串长度无关紧要。

关于 2 字节字符，你是对的。拉丁字符集也会导致问题，但是混合大小写(大写和小写)的问题可以通过屏蔽掉第 5 位 (32) 以转换为大写(或与 32 进行或运算以转换​​为小写)来轻松解决。

ASCII 字符表为所有字符分配一个整数:

@ = 64 = 01**0**00000   ...  
A = 65 = 01**0**00001   ...   a =  97 = 01**1**00001
B = 66 = 01**0**00010   ...   b =  98 = 01**1**00010 
.. 
Z = 90 = 01**0**11010   ...   z = 122 = 01**1**11010

大写和小写字符仅在特定位不同，'a' - 32 == 'A' 或相反:'B' + 32 == 'b ' 或 'B' | 32 == 'b'，其中 | 是按位或运算符。