面试题 01.01. 判定字符是否唯一（优质解法）

链接：面试题 01.01. 判定字符是否唯一

代码：

class Solution {
    public boolean isUnique(String astr) {
        //s[i]仅包含小写字母，数据范围小于 32 位，我们可以使用 int 变量的比特位来代替数组
        // 每个小写字符对应 bitMap 中的一个比特位，如 a 对应下标为 0 的比特位
        int bitMap=0;
        
        for(int i=0;i<astr.length();i++){
            int offset=astr.charAt(i)-'a';
            //检查之前是否有过 charStr[i] 字符，检查该偏移量下的比特位是否为1
            if(((bitMap>>offset)&1)==1){
                return false;
            }
            //之前没有该字符，添加该字符
            bitMap=bitMap|(1<<offset);
        }

        return true;
    }
}

题解：

? ? ? ? 本题属于很简单的一道题，有很多的解题方法，这里介绍一种不是太普遍的方法，通过位运算来解决该问题

? ? ? ? 首先我们要注意到一个条件，?s[i]?仅包含小写字母，也就是说字符串的组成只有 26 位小写字符，而一个 int 类型的变量的二进制位有 32 位，所以用一个二进制位来代表字符之前是否出现过是绰绰有余的

? ? ? ? 用 0 下标的二进制位代表 a，1 下标的代表 b ，以此类推

? ? ? ? 通过遍历获取到字符串中的一个字符后，要判断该字符之前是否出现过，即判断该字符所对应的二进制位是否为 1 ，比如现在得到了一个字符 b ，前四个二进制位为 0110 ，首先用字符 b - a 得到偏移量 1，让二进制位向右偏移 1 位，二进制位为 0011?此时 b 字符对应的二进制位移到了第一位，让 0011 & 1，得 1，代表 b 字符对应的二进制位为 1，说明之前 b 字符就存在于字符串中了，返回 false

0? ? ? ? 0? ? ? ? 1? ? ? ? 1

&

0? ? ? ? 0? ? ? ? 0? ? ? ? 1

=

0? ? ? ? 0? ? ? ? 0? ? ? ? 1

? ? ? ? 如果前四个二进制位为 0101 b 字符对应的二进制位为 0 ，代表之前 b 字符没有出现过，现在就要将 b 字符对应的二进制位改为 1，偏移量 offset = b - a = 1，0101 | 0010 = 0111 ，此时除了 b 字符对应的二进制位变为 1 ，其余的二进制位都没有改变，而 0010 可以由 1 << offset 得到

? ? ? ? 以上便是通过位运算来解决该问题的核心内容