leetcode算法之位运算

1.判断字符是否唯一

判断字符是否唯一

class Solution {
public:bool isUnique(string astr) {//利用鸽巢原理做优化if(astr.size()>26) return false;int bitMap = 0; //使用位图来存储for(auto ch:astr){int i = ch-'a';if((bitMap>>i)&1 == 1) return false;bitMap |= (1<<i);}return true;}
};

2.丢失的数字

丢失的数字

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

3.两整数之和

两整数之和

class Solution {
public:int getSum(int a, int b) {while(b!=0){int x = a^b;unsigned int carry = (unsigned int)(a&b)<<1;a = x;b = carry;}return a;}
};

4.只出现一次的数字II

只出现一次的数字II

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<<i);}}return ret;}
};

5.消失的两个数字

消失的两个数字

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {//将所有的数异或在一起int tmp = 0;for(auto x:nums) tmp^=x;for(int i=1;i<=nums.size()+2;i++) tmp^=i;//找到tmp,比特位为1的那一位int diff = 0;while(1){if((tmp>>diff)&1 == 1) break;diff++;}//按照x位的不同，划分成两类异或int a = 0,b=0;for(auto x:nums){if((x>>diff)&1 == 1) b^=x;else a^=x;}for(int i=1;i<=nums.size()+2;i++){if((i>>diff)&1 == 1) b^=i;else a^=i;}return {a,b};}
};

6.位1的个数

位1的个数

class Solution {
public:int hammingWeight(uint32_t n) {int sum = 0;for(int i=0;i<32;i++){if((n>>i)&1 == 1) sum++;}return sum;}
};

7.比特位计数

比特位计数

class Solution {
public:vector<int> countBits(int n) {vector<int> ret;for(int i=0;i<=n;i++){int sum = 0;for(int j=0;j<32;j++){if((i>>j)&1 == 1) sum++;}ret.push_back(sum);}return ret;}
};

8.汉明距离

汉明距离

class Solution {
public:int hammingDistance(int x, int y) {int sum = 0;int temp = x^y;for(int i=0;i<32;i++){if((temp>>i)&1 == 1) sum++;}return sum;}
};