Leetcode 判断字符是否唯一
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
示例 1：
1
2
| 输入: s = "leetcode"
输出: false
|
示例 2：
限制：
0 <= len(s) <= 100 s[i]仅包含小写字母- 如果你不使用额外的数据结构，会很加分。
Related Topics
位运算哈希表字符串排序👍 324
👎 0
ans:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| 不适用数据结构 则使用位运算最合适
分别是 (num & (1 << index)) != 0 以及 num |= (1 << index)，读者可先看完代码，有不理解的再看下我重点讲解的两行代码。
index 1 << index 解释
0 0000 0001 << 0 1左移 0 位为 0000 0001 = 1
1 0000 0001 << 1 1左移 1 位为 0000 0010 = 2
2 0000 0001 << 2 1左移 2 位为 0000 0100 = 4
3 0000 0001 << 3 1左移 3 位为 0000 1000 = 8
......
7 0000 0001 << 7 1左移 7 位为 1000 0000 = 128
研究 num & (1 << index)
首先1 << index 由 一个 1 和多个 0 组成，num 是 int 型，假设 index = 1，即将 1 左移一位，此时 1 << index 为 ... 0000 0010，任何数 & 0 都为 0，所以num & (1 << 1)表示的是 num 化为二进制后的第二位与 1 << index 的第二位 & 的结果。
假设 num 为 0， 则 (... 0000 0000 & ... 0000 0010) = 0，从哈希表的角度看就是 num 的第二位未被使用，假设位数对应26个小写字母，第二位为b，即hash中不存在b;
假设 num 为 2，则 (... 0000 0010 & ... 0000 0010) = 2，从哈希表的角度看就是 num 的第二位已被使用，假设位数对应26个小写字母，第二位为b，即hash中已存在b;
研究 num |= (1 << index)
num | 1 << index
0 | 1 = 1
0000 0000 | 0000 0001 = 1
1 | 1 = 1
0000 0001 | 0000 0001 = 1
2 | 1 = 3
0000 0010 | 0000 0001 = 3
当 num = 2 时，表明字母 b 已出现过，当 index = 0，1 << index 表示左移 0 位，对应字母 a，此时num |= (1 << index) 为 3，从哈希表的角度来看，此时 num 相当于已存在字母 a 和 b， 此时 num & (1 << 0) 为 1 不等于 0 ，表明字母 a 已经存在，返回false
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class soluaction{
public boolean getResult(String str){
int length = str.length();
if(length > 26) return false;
int num =0;
for(int i=0;i< len ;i++){
char c = str.charAt(i);
int index = c -'a';
if((num & 1 << index) !=0){
return false;
}else{
num != 1 << index;
}
}
return true;
}
}
|
__END__
