遵义市汇川区建设厅网站,网站建设的费用计什么科目,佳木斯网站网站建设,苏州企业网站建站系统文章目录 前言丢失的数字两整数之和只出现一次的数字II消失的两个数字总结 前言 上一篇博客#xff0c;我们已经把位运算的基础知识#xff0c;以及基本运算都掌握啦 上次的习题还是让人意犹未尽#xff0c;今天我们来尝试一下难一点的题目 位运算熟练起来真的让人觉得做题是… 文章目录 前言丢失的数字两整数之和只出现一次的数字II消失的两个数字总结 前言 上一篇博客我们已经把位运算的基础知识以及基本运算都掌握啦 上次的习题还是让人意犹未尽今天我们来尝试一下难一点的题目 位运算熟练起来真的让人觉得做题是一种享受 fellow me 丢失的数字
丢失的数字 思路 少了一个数字给他找回来不就好了吗 让我想到直接对数组 按位异或 一遍 然后再对 0-n 按位异或一遍出现两次的都消消乐 剩下的就是我们要找的数字
class Solution
{
public:int missingNumber(vectorint 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(vectorint 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:vectorint missingTwo(vectorint 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进行分组分别异或数组和完整序列得到两数。 心得 位运算题目需灵活运用位操作性质如异或消重、与运算找进位、按位统计等 通过分解问题、逐步处理能将复杂问题简化然后逐个击破 今天的内容就到这里啦不要走开小编持续更新中~~~~
