目录
一认识位运算
二判定字符是否唯一
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; // 判断是否为1
else
hash = 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}; // 数组模拟hash
int 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;
else
b ^= 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;
else
b ^= e;
}
for (int i = 1; i <= nums.size() + 2; i++)
{
if (((i >> differ) & 1) == 1)
a ^= i;
else
b ^= i;
}
return {a, b};
}
};以上便是位运算相关的题目，有问题欢迎在评论区中指出，谢谢！