您的位置:首页 > 游戏 > 手游 > 【位运算】--- 进阶题目赏析

【位运算】--- 进阶题目赏析

2024/12/23 11:59:10 来源:https://blog.csdn.net/2301_79448270/article/details/141790402  浏览:    关键词:【位运算】--- 进阶题目赏析

 Welcome to 9ilk's Code World

       

(๑•́ ₃ •̀๑) 个人主页:        9ilk

(๑•́ ₃ •̀๑) 文章专栏:     算法Journey 


本节我们来赏析位运算的一些进阶题目。


🏠 只出现一次的数字II

📌 题目解析

只出现一次的数字II

📌 算法原理

✏️ 思路一:哈希表+异或

由题目意思可得,除了只出现一次的数字之外,其他数字都出现了三次,我们可以利用哈希表,我们遍历一遍数组,将这些数异或用ret记录,当某个数出现三次时,我们再用ret异或这个数,最后得到的结果就是只出现一次的数字,因为其他数字在我们操作下都出现了四次被异或为0。

参考代码:

class Solution {
public:int singleNumber(vector<int>& nums){unordered_map<int,int> hash;int ret = 0; for(const auto& e : nums){hash[e]++;ret ^= e;if(hash[e] == 3) //出现三次再次异或ret ^= e;}      return ret; }
};

✏️ 思路二: bit位分组

由于其他数字都出现3次,因此我将数组中每个数特定bit位相加,对于出现过三次的这些数,他们特定bit位相加得到的一定是3的倍数,%3得到0,最后数组中所有数加完后再%3得到的一定是只出现一次那个数字上的bit位的数字.因此,我们可以不断向左移,对每个bit位进行这样的操作,就能得到只出现一次数字的完整bit位了.

参考代码:

class Solution {
public:int singleNumber(vector<int>& nums){ int ret  = 0;for(int i = 0 ; i < 32 ; i++){int sum = 0;for(int x : nums){if((x>>i)&1) sum++;}sum %= 3;//得到的是只出现一次数字i位上的数字if(sum == 1) ret |= (1 <<i);}return ret; }
};

拓展 : 如果其他数出现n次,另外一个数字出现m次,我们同样可以利用这种方式来找出不同点(%n)从而来找到只出现一次的数字.

🏠 只出现一次的数字III

📌 题目解析

只出现一次的数字III

  • -2^31 <= nums[i] <= 2^31 - 1 注意数据范围过大使用int可能会导致数据溢出。

📌 算法原理

由图中我们可以知道,ret最后一定是两个只出现一次的数字(记为a和b)的异或,由于异或是相同为0,相异为1,因此我们可以利用n&(-n)提取异或后的ret最右边的1,也就是a和b在这个bit位上的数字不同,依照这个不同可以将原数组中的数字划分为两种:一种是k位上是1,一种是k位上是0,由于其他数字出现了两次他们异或之后得到的一定是0,最后ret1和ret0得到的一定是只出现一次的两个数字。

参考代码:

class Solution 
{
public:typedef long long ll;vector<int> singleNumber(vector<int>& nums){ll ret = 0;for(int i = 0 ; i < nums.size() ; i++){ret ^= nums[i]; //得到的是两个不同的数异或}//我们先找ret最右边的1因为异或相异为1 这样就可以依照这个把a分到这一位上有0/1,b分到这一位有1/0ll k = ret & (-ret);//用k判断某一位是1还是0ll ret1 = 0;ll ret0 = 0;for(int i = 0 ; i < nums.size();i++){if(nums[i] & k) //说明该位上为1ret1 ^= nums[i];elseret0 ^= nums[i];}return {(int)ret1,(int)ret0};}
}s2;

🏠 消失的两个数字

📌 题目解析

消失的两个数字

📌 算法原理

这道题其实就是丢失的数字 + 只出现一次的数字III。我们可以通过nums的数组长度知道未消失前数字的总数。异或一遍原来数字再异或一遍nums,就可以得到消失两个数字的异或。此时就转化为只出现一次的数字III,可以利用ret&(-ret)提取两者不同的bit位,依据不同再遍历一遍进行分组得到这两个数字。

参考代码:

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {int n = nums.size() + 2;int ret = 0;for(int i = 1 ; i <= n ; i++){ret ^= i;} for(auto& e : nums){ret ^= e;}// 1^4int k = ret & (-ret); //提取最右边的一个1 消失的两个数在第k位不同int ret1 = 0;int ret0 = 0;for(int i = 1 ; i <= n ; i ++){if(i & k)ret1 ^= i;elseret0 ^= i; }for(auto& e : nums){if(e & k)ret1 ^= e;elseret0  ^= e; }int max = 0;int min = ret0 > ret1 ? (max = ret0,ret1) : (max = ret1,ret0);return {min,max};}
};

完。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com