【C++算法】33.位运算_判定字符是否唯一

文章目录

• • 题目链接：
  • 题目描述：
  • 解法
  • C++ 算法代码：
  • 图解

题目链接：

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

题目描述：

解法

如果使用数据结构的话

1. 哈希表：

一个一个字符扫描，不在哈希表里面的就放进去，在里面的就返回false。扫描完全部不重复就返回true。

也可以优化一下，字母一共26个，可以搞个数组hash[26]

---

位图

可以用26个0和1来表示，0表示没出现过，1表示出现过。

优化：

使用位图前检查字母长度是不是>26，是的话就直接返回false。

C++ 算法代码：

class Solution 
{
    public:
    bool isUnique(string astr) 
    {
        // 利用鸽巢原理来做的优化
        if(astr.size() > 26) return false; 
        int bitMap = 0;
        for(auto ch : astr)
        {
            int i = ch - 'a';
            // 先判断字符是否已经出现过
            if(((bitMap >> i) & 1) == 1) return false;
            // 把当前字符加入到位图中
            bitMap |= 1 << i;
        }
        return true;
    }
};

图解

例如：s = "leetcode"

1. astr.size() < 26

   bitMap就是位图，初始化为0，表示所有字符都尚未出现。

   进入循环，

   字符 ‘l’ 对应的索引 i = 'l' - 'a' = 11。
   检查 bitMap 的第 11 位：
   bitMap = 0，第 11 位为 0。
   将第 11 位置为 1：
   bitMap = 0 | (1 << 11) = 2048。

2. 进入循环，

   字符 ‘e’：
   字符 ‘e’ 对应的索引 i = 'e' - 'a' = 4。
   检查 bitMap 的第 4 位：
   bitMap = 2048，第 4 位为 0。
   将第 4 位置为 1：
   bitMap = 2048 | (1 << 4) = 2112。

3. 进入循环，

   字符 ‘e’：
   字符 ‘e’ 对应的索引 i = 'e' - 'a' = 4。
   检查 bitMap 的第 4 位：
   bitMap = 2112，第 4 位为 1（之前已经设置为1）。
   发现重复字符 e，函数返回 false。