检查字符串中的重复字符

在采访中，我被要求检查给定的字符串有重复字符的天气。谷歌关于这个问题，我来了解一个使用位操作的问题。检查字符串中的重复字符

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字节宽字符），这将工作吗？

来源

2012-11-08 YS.

该算法使用1位ASCII字符来指示该集合的存在。所以它至少适用于英文小写字母 - 其中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'，其中|是按位OR运算符。

来源

2012-11-08 07:16:45

非常感谢真正的解释。但是你能否详细说一下小写和大写的情况。 –

这就是所谓的位掩码。这里的检查器是位掩码。

第一个表达式:if((checker&(1<<val))>0)获取该位，第二个表达式checker|=(1<<val)设置该位。

左移运算符提高了2^val。所以你有类似于001000（'d'）的东西。

&运算符只要检查者的第i位和新的val（001000）都是1就返回true。所以你知道该字符是否已被覆盖。

The |运算符简单地将第i位设置为1。因此，如果在某些情况下检查器是010000，现在它变成011000.

来源

2012-11-08 07:25:52

检查字符串中的重复字符

回答

相关问题