文章目录
- 前言
- 丢失的数字
- 两整数之和
- 只出现一次的数字II
- 消失的两个数字
- 总结
前言
上一篇博客，我们已经把位运算的基础知识，以及基本运算都掌握啦
上次的习题还是让人意犹未尽，今天我们来尝试一下难一点的题目
位运算熟练起来真的让人觉得做题是一种享受
fellow me
丢失的数字
丢失的数字
思路：
少了一个数字，给他找回来不就好了吗
让我想到直接对数组 按位异或 一遍， 然后再对 0-n 按位异或一遍，出现两次的都消消乐
剩下的就是我们要找的数字
class Solution
{
public:int missingNumber(vector<int>& nums) {int ans = 0;for(auto x : nums){ans ^= x; // 按位异或当前数组}for(int i = 0; i <= nums.size(); i++){ans ^= i; // 重新按位异或一遍 0-n}return ans;}
};
两整数之和
两整数之和
思路：
乍一看，不让我用运算方法，那不是完蛋了吗
但仔细想想，这不是学了位运算，前面了解到按位异或（^）是无进制加法，按位与（&）是进位
其实可以组合起来使用，我们先算出无进位相加的结果，然后再找出进位，给他加上，再如此反复循环，直到没有进位
class Solution
{
public:int getSum(int a, int b) {while(b != 0){int x = a ^ b; // 无进位相加// 这里无符号 是防止溢出 unsigned int cur = (unsigned int) (a & b) << 1; // 找出进位a = x;b = cur;}return a;}
};
就这么几行，想明白了，还是很简单的
只出现一次的数字II
只出现一次的数字II
思路：
一眼hash直接秒了，但是题目要求常数级空间。。。。。
设要找的数位 ret
由于整个数组中，需要找的元素只出现了「一次」，其余的数都出现的「三次」，因此我们可以根据所有数的「某一个比特位」的总和 %3 的结果，快速定位到 ret 的「一个比特位上」的值是0 还是 1
这样，我们通过 ret 的每一个比特位上的值，就可以将 ret 给还原出来
class Solution
{
public:int singleNumber(vector<int>& nums) {int ret = 0;for(int i = 0; i < 32; i++){int sum = 0;for(auto x : nums){if(((x >> i) & 1) == 1) // 判断当前比特位{sum++; // 累积个数}}sum %= 3;if(sum == 1) // 符合条件就把ret当前的比特位置为 1{ret = ret | 1 << i;}}return ret;}
};
做完发现位运算真好奇妙
消失的两个数字
消失的两个数字
最后一题hard难度结尾吧
思路：
缺了两个数字，想到前面热乎的缺一个数字，我们可以按位异或两遍给他找出来，但是找出来的是两个数字的异或
所以我们还要处理这两个数字的异或，分解他们，又想到我们上一次做过的（两个只出现一次的数字）
好像就是两个题目的融合，才让他到了hard的难度
class Solution
{
public:vector<int> missingTwo(vector<int>& nums) {int ans = 0;for(auto x : nums)ans ^= x;for(int i = 1; i <= nums.size() + 2; i++)ans ^= i;// 现在找到了两个数字的异或int x = 0, y = 0;ans = ans & (-(long long)ans); // 提起ans二进制最右侧的 1for(auto i : nums) // 分组异或 { if((i & ans) == ans)x ^= i;elsey ^= i;}for(int i = 1; i <= nums.size() + 2; i++)// 分组异或{if((i & ans) == ans)x ^= i;elsey ^= i;}return {x, y};}
};
prefect 位运算完美收官
总结
今天通过几道位运算题目，巩固了位运算的应用技巧：
- 丢失的数字
利用异或性质，两次异或数组和0~n的数，出现两次的抵消，剩下的即为缺失数。 - 两整数之和
通过异或（无进位加法）和与运算左移（进位）模拟加法，循环处理进位直至为零，注意用unsigned避免溢出。 - 只出现一次的数字II
统计每一位1的个数，模3后确定目标数各位的值，逐位组合得到结果。 - 消失的两个数字
结合异或和分组思想，先找到两数异或结果，提取最右1进行分组，分别异或数组和完整序列得到两数。
心得
位运算题目需灵活运用位操作性质，如异或消重、与运算找进位、按位统计等
通过分解问题、逐步处理，能将复杂问题简化，然后逐个击破
今天的内容就到这里啦，不要走开，小编持续更新中~~~~
