题解：判断字符是否唯一(位运算算法)
1.题目
题目链接：LINK
2.题解
题解有两种方法，
一是做一个哈希数组，去查重；
二是直接用一个变量每一位来对应表示是否有这个字母即可(位图算法)。
下面仅说位图算法：
3.位图参考代码
class Solution { public: bool isUnique(string astr) { if(astr.length() > 26) return false;// 鸽巢原理 int ret = 0;//32个比特位全是0 for(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
