檢查字符串中的重複字符

在採訪中，我被要求檢查給定的字符串有重複字符的天氣。谷歌關於這個問題，我來了解一個使用位操作的問題。檢查字符串中的重複字符

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

檢查字符串中的重複字符

回答

相關問題