初识算法 · 位运算(2)

目录

前言：

判定字符是否唯一

丢失的数字

比特位计数

只出现一次的数字III

---

前言：

​本文的主题是位运算，通过四道题目讲解，一道是判断字符是否唯一，一道是只出现一次的数字III，一道是比特位计数，一道是丢失的数字。
链接分别为：

338. 比特位计数 - 力扣（LeetCode） 面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）

260. 只出现一次的数字 III - 力扣（LeetCode） 268. 丢失的数字 - 力扣（LeetCode）

因为这些题目都是比较简单的，所以一一揉在一起介绍。

那么，话不多说，直接进行主题咯。
​

---

判定字符是否唯一

这道题目是作为面试题目出现的，作为一道面试题目，它有很多解法，比如我们可以使用哈希映射，使用map 使用set，使用函数count就可以判断是否出现了两次，也可以使用数组，遍历一遍，看哪个下标对应的值是2就返回false即可，解法是非常非常多的，说白了，这道题目就是让我们判读这堆“数字”里面是否有重复的数字。

那么前两个方法，多多少少都用到了额外的数据结构，额外的空间，相对来说还是没有那么好，毕竟空间还是大了一点，我们不妨利用位图的思想，一个Int就可以搞定，遍历到的时候，将位图对应的位置置为1，再次如果判断到了，直接返回false即可。

当然了，这道题目可以使用鸽巢原理进行优化，一共才26个英文字符，如果字符串的长度超过了26，直接返回false即可。

以上是题目解析 + 算法原理，以下是原理编写：

class Solution 
{
public:bool isUnique(string astr) {int bitmap = 0;for(auto e : astr){int x = e - 'a';if(((bitmap >> x) & 1) == 1) return false;else bitmap |= (1 << x);}    return true;}
};

丢失的数字

题目十分简单，我们现在应该思考的是，我们可以用多少种解法，这道题目无非就是让我们从一个连续的数集里面找到缺失的数字就可以了。“那这道题不就是缺失的数字吗”

第一种解法，高斯求和，因为数字肯定是从0开始到n的，所以我们可以将0到n这段区间的所有的数字加起来，最后减去给我们的这段区间的和即可。时间复杂度为O(N) 空间复杂度为O(1)

第二种解法，哈希映射，我们就开一个n + 1的数组，遍历数组，对应下标+1，看谁为2即可。时间复杂度为O(N) 空间复杂度为O(N)，相对来说就不是那么好了。

第三种解法，遍历数组看i + 1是否为前一个数 + 1即可。

第四种解法，异或的运算律，数组的下标和数异或，看谁空出来了就可以了。

class Solution {
public:int missingNumber(vector<int>& nums) {        sort(nums.begin(),nums.end());if(nums[0] != 0) return 0;int i = 0;for(i = 0; i < nums.size() - 1; i++){if(nums[i] != (nums[i + 1] - 1)) return nums[i] + 1;}    return nums[i] + 1;}
};

对于第三种解法是比较差劲的，因为还是注意许多细节问题，比如需要先排序，还要判断1 2的这种情况，那么对于异或来说，就很不错了：

class Solution 
{
public:int missingNumber(vector<int>& nums) {int ret = 0;for(auto e : nums) ret ^= e;for(int i = 1;i <= nums.size();i++)ret ^= i;return ret;}
};

比特位计数

题目的要求是计算从0到n的所有的数中的二进制表示中1的个数，将个数插入到顺序表，然后返回就可以了。

那这道题不就是多次计算比特位中1的个数吗？我们甚至可以直接复用上篇那道题目的代码：

class Solution 
{
public:int countone(int n){int x = 0;while(n){n &= (n - 1);x++;}return x;}vector<int> countBits(int n) {vector<int> v;for(int i = 0; i <= n; i++){v.push_back(countone(i));}return v;}
};

只出现一次的数字III

这道题目无非就是找单身狗plus版本而已，就是缺失的数字嘛对吧！

我们需要找到两个数，那么异或整个数组肯定是少不了的，异或了之后，剩余的是两个数的异或结果，那么我们如何分离出来呢？

我们可以结合基本题目 ：提取最低位的1，提取出来之后，两个只出现一次的数字在该位上一定是不同的，因为异或出来结果是1，其他的数也异或掉了，所以一定是一个为1，一个为0。

那么我们利用这个特点，将数组中的每个数组和最低位的数字一&运算一下，就可以得到结果了，因为没有要求顺序，所以我们可以直接输出。

class Solution 
{
public:vector<int> singleNumber(vector<int>& nums) {//先将整个数组异或int ret = 0;for(auto e : nums) ret ^= e;//获取最低位的1->实际上是分组// int low_bit = ret & -ret;int low_bit = (ret == INT_MIN ? ret : ret & (-ret));//开始分组int ans1 = 0, ans2 = 0;for(auto e : nums){if(e & low_bit) ans1 ^= e;else ans2 ^= e;}return { ans1, ans2 };}
};

以上就是位运算的多个题目解析。

---

感谢阅读！