专题五——位运算

一认识位运算

二判定字符是否唯一

二丢失的数字

三两整数之和

四只出现一次的数字Ⅱ

五只出现一次的数字Ⅲ

六消失的两个数字

一认识位运算

二判定字符是否唯一

oj链接：判定字符是否唯一

解法：位图的思想（2,3点的结合应用）

class Solution
{
public:bool isUnique(string astr){int hash = 0;for (auto &s : astr){if (((hash >> (int)(s - 'a')) & 1) == 1)return false; // 判断是否为1elsehash = hash | (1 << s - 'a'); // 将对应的bit由0修改为1}return true;}
};

二丢失的数字

oj链接：丢失的数字

解法：1.hash表模拟；2等差数列求和；

3.位运算： 将数组中的数与0到n的数进行异或：相同的消失，结果就是答案！！

// 解法1：hash表
class Solution
{
public:bool hash[10001] = {0}; // 数组模拟hashint missingNumber(vector<int> &nums){int n = nums.size();for (int i = 0; i < n; i++)hash[nums[i]] = true;for (int i = 0; i <= n; i++){if (!hash[i])return i;}return -1; // 不可能出现}
};// 解法2：高斯求和
class Solution
{
public:int missingNumber(vector<int> &nums){int m = nums.size(), sum = 0;int n = m + 1, a1 = 0, an = m;sum = n * (a1 + an) / 2;for (auto &e : nums)sum -= e;return sum;}
};// 解法3：位运算
class Solution
{
public:int missingNumber(vector<int> &nums){// 单身狗问题int n = nums.size(), ret = 0, i = 0;for (; i < n; i++)ret ^= nums[i] ^ i;// 最后的i要参与异或ret ^= i;return ret;}
};

三两整数之和

oj链接：两整数之和

思路：如果面试题：return a+b; ~-~

运用异或 - > 无进位相加：

class Solution
{
public:int getSum(int a, int b){int Xor = 0, carry = 0;while (b != 0){Xor = a ^ b;carry = (a & b) << 1; // 找到进位位置(两个位置都是1),再<<1(把进位加上)a = Xor;              // 最终结果保存在a中！！b = carry;            // 为0(不出现两个bit都是1的情况)}return a;}
};

四只出现一次的数字Ⅱ

oj链接：只出现一次的数字 II

思路：1.hash表遍历；

2.找规律： 每一位位数之和 % 出现的最多次数 = 出现一次的位数的值

// 解法1:hash表
class Solution
{
public:int singleNumber(vector<int> &nums){unordered_map<int, int> hash;for (auto &e : nums)hash[e]++;for (auto &e : nums)if (hash[e] == 1)return e;return -1;}
};// 解法2：位运算
class Solution
{
public:int singleNumber(vector<int> &nums){int ret = 0;for (int i = 0; i < 32; i++){int sumbit = 0;for (auto &e : nums){if (((e >> i) & 1) == 1)sumbit++; // 统计第i个bit中1的个数}if (sumbit % 3 == 1)ret |= (1 << i); // 第i个bit总共个数%3 = 出现1次的元素的第i个bit的值}return ret;}
};

五只出现一次的数字Ⅲ

oj链接：只出现一次的数字 III

思路：1.先用变量tmp：将所有的数进行异或

2.在tmp中：（从右向左）找出bit位为1(相异位1)的位置：将所有数分为两部分；

该位置为1与该位置为0；将这两部分各自再次异或就分别得到了只出现一次的数字啦！

class Solution
{
public:vector<int> singleNumber(vector<int> &nums){int tmp = 0;for (auto &e : nums)tmp ^= e;int i = 0;for (; i < 32; i++){if (((tmp >> i) & 1) == 1)break;}int a = 0, b = 0;for (auto &e : nums){if (((e >> i) & 1) == 1)a ^= e;elseb ^= e;}return {a, b};}
};

六消失的两个数字

oj链接：面试题 17.19.消失的两个数字

思路：丢失的数字 + 只出现一的数字Ⅲ 的结合而已，超级简单！！

class Solution
{
public:vector<int> missingTwo(vector<int> &nums){int sum = 0;for (auto e : nums)sum ^= e;for (int i = 1; i <= nums.size() + 2; i++){sum ^= i;}int differ = 0;while (1){if (((sum >> differ) & 1) == 1)break;differ++;}int a = 0, b = 0;for (auto e : nums){if (((e >> differ) & 1) == 1)a ^= e;elseb ^= e;}for (int i = 1; i <= nums.size() + 2; i++){if (((i >> differ) & 1) == 1)a ^= i;elseb ^= i;}return {a, b};}
};