// O(N) - 沒有額外的數(shù)據(jù)結(jié)構(gòu)...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”有效。對(duì)于所有小寫字母字符串，它都有效，我也知道它是如何工作的。
3 回答
飲歌長嘯
TA貢獻(xiàn)1951條經(jīng)驗(yàn) 獲得超3個(gè)贊
好吧，答案可能取決于語言，但在 Java 中（JLS?15.19。移位運(yùn)算符）：
如果左側(cè)操作數(shù)的提升類型為
int，則僅將右側(cè)操作數(shù)的最低五位用作移位距離。就好像右邊的操作數(shù)是按位邏輯 AND 運(yùn)算符&（§15.22.1）和掩碼值0x1f(?0b11111)。因此，實(shí)際使用的移動(dòng)距離總是在0到 的范圍內(nèi)31，包括在內(nèi)。
所以就像你執(zhí)行c = c & 0x1f, or一樣c = c % 32，為了運(yùn)算符的目的，大寫A和小寫都a變成了 ,c的值。0<<
對(duì)于 32 位類型，我假設(shè)其他語言可能也有類似的工作方式int。
慕森王
TA貢獻(xiàn)1777條經(jīng)驗(yàn) 獲得超3個(gè)贊
另一種檢查字符串是否包含所有唯一字符的方法——在O(N)中：
使用無限循環(huán)
使用雙變量 i (i=0) 和 j=(n-1 [其中 n-是字符串長度])
檢查每個(gè)第 i 個(gè)字符是否等于第 j 個(gè)字符
3.1 if [i-th char == j-th && i != j char], break loop cause string contain duplicate chars. （i != j 表示比較相同的字符）
3.2 減少 j 并設(shè)置 j 為 n-1 和 i += 1，當(dāng) j = 0 [這部分很棘手]
重復(fù)第 3 步，除非 i 變成第 n-1 個(gè)大小
代碼
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貢獻(xiàn)1860條經(jīng)驗(yàn) 獲得超8個(gè)贊
我建議使用大小為 256 的數(shù)組來存儲(chǔ)每個(gè)字符的計(jì)數(shù)（假設(shè)有 256 個(gè)可能的字符），在循環(huán)開始時(shí)將其設(shè)置為值 0。然后，當(dāng)您獲取每個(gè)下一個(gè)字符時(shí)，只需簡(jiǎn)單地增加每個(gè)位置。最后，有一個(gè)快速 hack 檢查位置中的值是 0 還是 1（例如，freq[i] == !!freq[i])這個(gè) if 語句[freq[i] == !!freq[i]]應(yīng)該適用于數(shù)組中的所有 256 個(gè)項(xiàng)目。
更新：
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;
}
添加回答
舉報(bào)
0/150
提交
取消