2351-第一个出现两次的字母

🔗 链接

lc-2351

一道普通的字符串/数组类题目。第一时间想到可以用hash表。然后看到官方题解还有利用二进制数进行状态压缩的解法，尝试后也ac了，在此记录一下。

📋 代码1-hash表

使用占空间较小的boolean类型来保存。false表示未出现过，true表示出现过。

public char repeatedCharacter(String s) {
    boolean[] vis = new boolean[26];
    char c = ' ';
    for (int i = 0; i < s.length(); i++) {
        c = s.charAt(i);
        if (vis[c - 'a']) {
            break;
        } else {
            vis[c - 'a'] = true;
        }
    }
    return c;
}

• 时间复杂度：O(n)，其中 n 是字符串s的长度。
• 空间复杂度：O(1)。占用的空间为包含了26个字符的数组。

📋 代码2-状态压缩

如下放代码所示，(vis & (1 << x)) != 0)用于判断vis这个数字的二进制表示中，第x位的值是否为1，与操作的结果不为0，表示第x位的值为1，即表示c这个字符出现过，返回c。否则，使用vis |= (1 << x)，把vis的第x为改为1。

int vis, x;
char c;
public char repeatedCharacter(String s) {
    for (int i = 0; i < s.length(); i++) {
        c = s.charAt(i);
        x = c - 'a';
        if ((vis & (1 << x)) != 0) {
            return c;
        }
        vis |= (1 << x);
    }
    return ' ';
}

• 时间复杂度：O(n)，其中 n 是字符串s的长度。
• 空间复杂度：O(1)。