《算法题讲解指南：优选算法-位运算》--33.判断字符是否唯一，34.丢失的数字
🔥小叶-duck：个人主页
❄️个人专栏：《Data-Structure-Learning》
《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--从优选到贪心
✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游
目录
位运算基础前置知识：
回顾了上面位运算基础前置的知识这里有五道非常简单的题可以试试手，都是考察位运算的题目：
位1的个数
191. 位1的个数 - 力扣（LeetCode）
C++算法代码：
class Solution { public: int hammingWeight(int n) { int count = 0; while(n) { n &= (n - 1); count++; } return count; } };比特位计数
338. 比特位计数 - 力扣（LeetCode）
C++算法代码：
class Solution { public: vector<int> countBits(int n) { vector<int> ans(n + 1, 0); for(int i = 0; i <= n; i++) { int count = 0; int num = i; while(num) { num &= (num - 1); count++; } ans[i] = count; } return ans; } };汉明距离
461. 汉明距离 - 力扣（LeetCode）
C++算法代码：
class Solution { public: int hammingDistance(int x, int y) { int count = 0; int ret = x ^ y; while(ret) { ret &= (ret - 1); count++; } return count; } };只出现一次的数字
136. 只出现一次的数字 - 力扣（LeetCode）
C++算法代码：
class Solution { public: int singleNumber(vector<int>& nums) { int val = 0; for(auto e : nums) { val ^= e; } return val; } };只出现一次的数字|||
260. 只出现一次的数字 III - 力扣（LeetCode）
C++算法代码：
class Solution { public: if(nums.size() == 2) { return nums; } sort(nums.begin(), nums.end()); vector<int> res; int ans = 0; for(int i = 0; i < nums.size(); i++) { ans ^= nums[i]; } for(int i = 0; i < nums.size(); i += 2) { if(nums[i] != nums[i + 1]) { res.push_back(nums[i]); ans ^= nums[i]; break; } } res.push_back(ans); return res; } };34. 判断字符是否唯一
题目链接：
面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）
题目描述：
题目示例：
解法（位图的思想）：
算法思路：
利用【位图】的思想，每一个【比特位】代表一个【字符，一个 int 类 型的变量 32 位足够表示所有的小写字母。比特位里面如果是 0，表示这个字符没有出现过。比特位里面的值是 1，表示该字符出现过。
那么我们就可以用一个【整数】来充当【哈希表】。
C++算法代码：
class Solution { public: bool isUnique(string astr) { //解法一：数组模拟实现哈希表 //解法一通过模拟实现哈希表来存放每个字符映射到数组的对应位置 //代码非常简单，这里就不演示了，而且因为需要额外使用数据结构不算加分项 //解法二：位图(不需要使用额外的数据结构) if(astr.size() > 26) { return false; } int m = 0; //作为比特位哈希表，通过一个数的二进制表示每个比特位存放对应的字符 for(int i = 0; i < astr.size(); i++) { //先判断当前字符是否在比特位哈希表中存在过 if(m >> (astr[i] - 'a') & 1) { return false; } //如果判断为假则该字符没有出现过，则相对应的比特位从0变成1 m = m | (1 << (astr[i] - 'a')); } return true; } };算法总结及流程解析：
35. 丢失的数字
题目链接：
268. 丢失的数字 - 力扣（LeetCode）
题目描述：
题目示例：
解法（位运算）：
算法思路：
设数组的大小为 n ，那么缺失之前的数就是【0，n】，数组中是在【0，n】中缺失一个数形成的序列如果我们把数组中的所有数，以及【0，n】中的所有数全部【异或】在一起，那么根据【异或】运算的【消消乐】规律，最终的异或结果应该就是缺失的数。
C++算法代码：
class Solution { public: int missingNumber(vector<int>& nums) { //解法一：高斯求和 // int ret = 0; // for(int i = 0; i < nums.size(); i++) // { // ret += (i + 1); // ret -= nums[i]; // } // return ret; //解法二：位运算 int ret = 0; for(int i = 0; i < nums.size(); i++) { ret ^= nums[i] ^= (i + 1); } return ret; } };算法总结及流程解析：
结束语
到此，33.判断字符是否唯一，34.丢失的数字 这两道算法题就讲解完了。通过两道经典例题讲解位图与异或技巧。33题利用位图思想，用整数比特位标记字符出现情况，实现O(1)空间复杂度判断字符唯一性。34题运用异或消消乐特性，通过数组与完整序列异或找出缺失数字。希望大家能有所收获！
