【算法】位运算算法——判断字符是否唯一

题解：判断字符是否唯一(位运算算法)

1.题目

题目链接：LINK

2.题解

题解有两种方法，
一是做一个哈希数组，去查重；
二是直接用一个变量每一位来对应表示是否有这个字母即可(位图算法)。

下面仅说位图算法：

3.位图参考代码

class Solution {
public:bool isUnique(string astr) {if(astr.length() > 26) return false;// 鸽巢原理int ret = 0;//32个比特位全是0for(auto& ch : astr){int n = ch - 'a';// 查重if(((ret >> n) & 1) == 1) return false;// 加入ret中ret = (ret | (1 << n));}return true;}
};

4.细节

鸽巢原理：
这里如果一个string的长度 > 26 且 都为小写字母的话，那么一定有重复的，所以可以不用判断直接返回false。

5.总结

用位图比哈希数组更加节约空间，直接把O(N)的空间复杂度降成了O(1)…

---

EOF