// O(N) - 沒有額外的數據結構...private boolean isUniqueWithoutDS(String str){ boolean value = true; int checker = 0; for (int i = 0; i < str.length(); i++) { int c = str.charAt(i) - 'a'; System.out.println("checker is : " + checker); System.out.println("1<<c is " + (1<<c)); if((checker & (1 << c))>0){ value = false; break; } checker = checker | 1<<c; } return value;}這是我的代碼并且工作正常，我無法理解它如何處理大寫字母和小寫字母組合的字符串。例如“ Zizu”有效。對于所有小寫字母字符串，它都有效，我也知道它是如何工作的。
3 回答
飲歌長嘯
TA貢獻1951條經驗 獲得超3個贊
好吧，答案可能取決于語言，但在 Java 中（JLS?15.19。移位運算符）：
如果左側操作數的提升類型為
int，則僅將右側操作數的最低五位用作移位距離。就好像右邊的操作數是按位邏輯 AND 運算符&（§15.22.1）和掩碼值0x1f(?0b11111)。因此，實際使用的移動距離總是在0到 的范圍內31，包括在內。
所以就像你執行c = c & 0x1f, or一樣c = c % 32，為了運算符的目的，大寫A和小寫都a變成了 ,c的值。0<<
對于 32 位類型，我假設其他語言可能也有類似的工作方式int。
慕森王
TA貢獻1777條經驗 獲得超3個贊
另一種檢查字符串是否包含所有唯一字符的方法——在O(N)中：
使用無限循環
使用雙變量 i (i=0) 和 j=(n-1 [其中 n-是字符串長度])
檢查每個第 i 個字符是否等于第 j 個字符
3.1 if [i-th char == j-th && i != j char], break loop cause string contain duplicate chars. （i != j 表示比較相同的字符）
3.2 減少 j 并設置 j 為 n-1 和 i += 1，當 j = 0 [這部分很棘手]
重復第 3 步，除非 i 變成第 n-1 個大小
代碼
String s = "abcde";
int i = 0;
int j = s.length()-1;
boolean flag = true;
while(true) {
if(i == s.length()-1)
break;
// DUPLICATE FOUND
if(i != j && s.charAt(i) == s.charAt(j)) {
flag = false;
break;
}else {
j--;
// COMPARING DONE AGAINST i-TH CHAR TO ALL OTHER CHARS, INCREMENT i NOW
if(j == 0) {
j = s.length()-1;
i += 1;
}
}
}
if(flag)
System.out.println("unique");
else
System.out.println("non-unique");
桃花長相依
TA貢獻1860條經驗 獲得超8個贊
我建議使用大小為 256 的數組來存儲每個字符的計數（假設有 256 個可能的字符），在循環開始時將其設置為值 0。然后，當您獲取每個下一個字符時，只需簡單地增加每個位置。最后，有一個快速 hack 檢查位置中的值是 0 還是 1（例如，freq[i] == !!freq[i])這個 if 語句[freq[i] == !!freq[i]]應該適用于數組中的所有 256 個項目。
更新：
unsigned int isDistinctStr(char *str);
unsigned int isDistinctStr(char *str) {
unsigned int ct, freq[256], i, j;
char ch;
for (i = 0; i < 256; i++) {freq[i] = 0;}
for (ct = 0; ch = *str; str++) {
j = (unsigned int) (ch & 0xffu);
freq[j]++;
}
for (j = 0; j < 256; j++) {
if (freq[j] == !!freq[j]) {ct++;}
}
return (ct == 256) ? 1 : 0;
}
添加回答
舉報
0/150
提交
取消