判定字符是否唯一

题目链接

题解

1. 哈希表，创建26个空间大小的哈希表
2. 位图，小写字符只有26个，位图可以存32个0或1，(bitMap >> i) & 1 判断是否存在元素，bitMap |= (1 << i)把元素加入到位图中

代码

class Solution 
{
public:bool isUnique(string astr) {// 位图// >26个字符说明存在重复的字符了// 优化int n = astr.size();if(n > 26) return false;int bitmap = 0;for(auto ch : astr){int i = ch - 'a';// 判断是否存在重复元素if((bitmap >> i) & 1) return false;// 不存在重复的元素就加入到位图中bitmap |= (1 << i);}return true;}
};

丢失的数字

题目链接

题解

1. 哈希表，开大小为n+1的空间，把所有的数加入到哈希表中，如果这个数没有出现，就是丢失的数
2. 高斯求和，（首项加尾项）* 项数 /2 - 数组中元素的和3
3. 位运算，用一个变量异或0到n的所有的数，再和数组中的数异或，就可以找到缺失的数

代码

class Solution 
{
public:int missingNumber(vector<int>& nums) {int n = nums.size();int sum = 0;for(int i = 0;i <= n;i++) sum ^= i;for(int i = 0;i < n;i++){sum ^= nums[i];}return sum;}
};

两整数之和

题目链接

题解

1. a ^ b无进位相加，(a & b) << 1进位，直到进位为0，就是答案

代码

class Solution 
{
public:int getSum(int a, int b) {// 异或(无进位相加) &并且左移一位求进位,进位到下一位上// 直到进位为0,就时最终答案int k = (a & b) << 1;int sum = a ^ b;while(k){a = sum;b = k;// 无进位相加sum = a ^ b;// 进位k = (a & b) << 1;}return sum;}
};

只出现一次的数字 II

题目链接

题解

1. 每个数都出现了3次，有3n个数，和只存在一个的数的某个比特位相加，再模3就是和只出现一次的数的比特位是一样的
2. 因此只需要算出数组中每个数的二进制的每个位的加和，再模3就是只出现一次的那个数的每个二进制位

代码

class Solution 
{
public:int singleNumber(vector<int>& nums) {int bit = 0;int n = nums.size();for(int j = 0;j <= 31;j++){int sum = 0;for(int i = 0;i < n;i++){if(((nums[i] >> j) & 1) == 1) sum++; }sum %= 3;if(sum == 1) bit |= (1 << j);}return bit;// map<int,int> ret;// for(auto x : nums) ret[x]++;// for(auto y : nums)// {//     if(ret[y] == 1) return y;// }   // return -1;}
};

消失的两个数字

题目链接

题解

1. 根据x位的不同，如何划分为两类异或？
如果x位上为1的是一组，x为上是0的是一组
比如：第二组样例
010 010
011 011
001 100

001 ^ 100 = 101
x = 1
第一位上为1的是一组，是0的是一组
010 010 100 -> 100
011 011 001 -> 001
这样就得到了答案

代码

class Solution 
{
public:vector<int> missingTwo(vector<int>& nums) {// 1.先找出消失两个数异或的结果// 2.再分开消失的两个数// 这两个数异或的结果肯定不会是0,至少有一位是1// 那就根据这位划分为两类异或// 划分为这位是1的和0的int sum = 0;int n = nums.size();for(int i = 1;i <= n+2;i++) sum ^= i;for(int i = 0;i < n;i++) sum ^= nums[i];// 提取这个1int tmp = sum & (-sum);int k = 0;for(int i = 0;i < 32;i++) {if((tmp >> i) & 1){k = i;break;}}int m = 0,t = 0;for(int i = 0;i < n;i++){if((nums[i] >> k) & 1) m ^= nums[i];else t ^= nums[i];}for(int i = 1;i <= n + 2;i++){if((i >> k) & 1) m ^= i;else t ^= i;}return {m,t};// vector<int> ret;// int hash[30010] = {0};// int n = nums.size();// for(int i = 0;i < n;i++)// {//     hash[nums[i]]++;// }// for(int i = 1;i <= n+2;i++) // {//     if(hash[i] == 0) ret.push_back(i);// }// return ret;}
};

总结

1. 给你一个数n，确定这个数的二进制表示上的第x位是0还是1？
(n>>x) & 1，== 0就是0，==1就是1
2. 将一个数n的二进制表示的第x位修改为1?
n = n | (1 << x)
3.将一个数n的二进制表示的第x为修改为0?
n = n & ~(1 << x)
4. 提取一个数n二进制表示中的最右侧的1？
n & (-n) 左侧被n取反后再按位与之后都变成了0，1的右侧都加1都变成了0
5. 干掉一个数n二进制表示中最右侧的1？
n & (n-1) 减一之后会向左边借1，借位的位置变为了0，它的右侧都变成了1，再按位与之后包括它本身都会变成0
6. 异或运算的规律
0 ^ a = a
0 ^ 0 = 0
a ^ a = 0
7. 位图总结
位图可以看成可以存32个二进制位的数组，(bitMap >> i) & 1 判断这一位是否存在，如果存在就加入到位图中，bitMap |= (1 << i)
8. 基础位运算
& | ^ ~ >> <<
9.运算符的优先级
如果判断不了运算符的优先级，就直接加括号