[每日一题]2351.第一个出现两次的字母
LeetCode.2351.第一个出现两次的字母 给你一个由小写英文字母组成的字符串 s ，请你找出并返回第一个出现 两次 的字母。
注意：
- 如果
a的 第二次 出现比b的 第二次 出现在字符串中的位置更靠前，则认为字母a在字母b之前出现两次。s包含至少一个出现两次的字母。
First Solution
class Solution {
public char repeatedCharacter(String s) {
char[] chars = s.toCharArray();
char result = ' ';
HashSet<Character> set = new HashSet<>();
for (int i = 0; i < chars.length; i++) {
set.add(chars[i]);
if (set.size() != i+1){
result = chars[i];
break;
}
}
return result;
}
}
class Solution {
public char repeatedCharacter(String s) {
Set<Character> charSet = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (charSet.contains(c)) {
return c;
} else {
charSet.add(c);
}
}
return s.charAt(0);
}
}
emmmm，第二个方法显然比我的要高级一点。
官方还给了一个状态压缩的方法：
我们注意到字符集的大小为 26，因此我们可以使用一个 32 位的二进制数 seen完美地存储哈希表。如果 seen 的第 i (0≤i<26) 位是 1，说明第 i个小写字母已经出现过。
具体地，我们对字符串 s 进行一次遍历。当遍历到字母 c 时，记它是第 i 个字母，seen 的第 i (0≤i<26) 位是 1，我们返回 c 作为答案即可；否则，我们将 seen 的第 i 位置为 1。
class Solution {
public char repeatedCharacter(String s) {
int seen = 0;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
int x = ch - 'a';
if ((seen & (1 << x)) != 0) {
return ch;
}
seen |= (1 << x);
}
}
}