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

2023-12-23 19:31:44

链接:面试题 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 得到

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

文章来源:https://blog.csdn.net/q322359/article/details/135172494
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。