优选算法第五讲:位运算模块
- 1.常见的位运算总结
- 2.判断字符是否唯一
- 3.丢失的数字
- 4.两整数之和
- 5.只出现一次的数字II
- 6.消失的两个数字
1.常见的位运算总结
2.判断字符是否唯一
链接: link
class Solution {
public:bool isUnique(string astr) {if(astr.size() > 26) return false;int hash = 0;for(auto e : astr){ //找出下标int i = e-'a';if(hash&(1<<i)) return false;//如果对应位置为1,证明前面已经存在了该字符,返回falseelse hash |= 1<<i;//将字符存储到int变量中}return true;}
};
3.丢失的数字
链接: link
class Solution {
public:int missingNumber(vector<int>& nums) {int sum = 0;for(auto e : nums) sum ^= e;for(int i = 0; i<=nums.size(); i++) sum ^= i;return sum;}
};
4.两整数之和
链接: link
class Solution {
public:int getSum(int a, int b) {while(b){int x = a^b;unsigned int carry = (unsigned int)(a&b)<<1;a = x;b = carry;}return a;}
};
5.只出现一次的数字II
链接: link
class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0;for(int i = 0; i<32; i++){int sum = 0;for(auto e : nums)if((e>>i)&1 == 1) sum++;// if((e & (1 << i)) == 1)// sum++;sum %= 3;if(sum == 1)ret |= 1<<i;}return ret;}
};
6.消失的两个数字
链接: link
class Solution {
public:vector<int> missingTwo(vector<int>& nums) {//先将nums中的所有数据进行异或int sum = 0;for(auto e : nums) sum ^= e;//然后再将1-N之内的数据进行异或for(int i = 1; i<=nums.size()+2; i++) sum ^= i;//找出最右边的1int rightone = sum&(-sum);int num1 = 0;for(auto e : nums)if(e & rightone)num1 ^= e;for(int i = 1; i<=nums.size()+2; i++)if(i & rightone)num1 ^= i;int num2 = sum^num1;return {num1, num2};}
};