35.两个整数之和
题目链接
题目描述
题目示例
解法（位运算）
算法思路
- 异或
^运算本质是【无进位加法】 - 按位与
&操作能够得到【进位】的对应位置，但还需要左移 1 才是需要进位的位置。 - 然后一直循环，直到【进位】变成 0 为止
C++算法代码
class Solution {
public:
int getSum(int a, int b) {
// 解法：位运算 (^异或：无进位相加)
while(b) {
int x = a ^ b;
int y = (a & b) << 1;
a = x;
b = y; // 得到进位的对应位置，再左移 1 才是需要进位的位置
// 只进行一次 a & b 不一定保证新的 a 和 b 没有需要进位的位置，所以需要将这个步骤进行循环
// a & b 为 0 则说明没有进位的位置了
}
return a ^ b;
}
};
算法总结及流程解析
36.只出现一次的数字 ||
题目链接
137. 只出现一次的数字 II - 力扣（LeetCode）
题目描述
题目示例
解法（比特位计数）
算法思路
设要找的数为 ret。由于整个数组中，需要找的元素只出现了【一次】，其余的数都出现【三次】，因此我们可以用根据所有数的【某一个比特位】的总和 %3 的结果，快速定位到 ret 上的【一个比特位上】的值是 0 还是 1。这样我们通过 ret 的每一个比特位上的值，就可以将 ret 还原出来。
C++算法代码
class Solution {
public:
int singleNumber(vector<int>& nums) {
// 方法一：排序 (时间复杂度较大:O(NlogN)，但容易想到)
// sort(nums.begin(), nums.end());
// for(int i = 0; i < nums.size() - 1; i += 3)
// {
// if(nums[i] != nums[i + 1])
// {
// return nums[i];
// }
// }
// return nums.back();
// 方法二：位运算 (为线性时间复杂度:O(32N)，但非常巧妙比较难想)
int ret = 0; // 作为位图
for(int i = 0; i < 32; i++) // 一个数二进制位的长度，依次修改 ret 的每一位
{
int sum = 0;
for(int x = 0; x < nums.size(); x++) // 计算 nums 中所有数的二进制第 i 位的和
{
sum += ((nums[x] >> i) & 1);
}
ret |= ((sum % 3) << i); // 求和结果余 3 后修改到 ret 对应第 i 位的位置
}
return ret;
}
};
算法总结及流程解析
37.消失的两个数字
题目链接
面试题 17.19. 消失的两个数字 - 力扣（LeetCode）
题目描述
题目示例
解法（位运算）
算法思路
本题相当于就是 268.丢失的数字 + 260.只出现一次的数字||| 组合起来的题。先将数组中的数和【1，n+2】区间内的所有数【异或】在一起，问题就变成了：有两个数出现了【一次】，其余所有的数出现了【两次】。进而变成了 260.只出现了一次的数字||| 这道题。
C++算法代码
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
// 位运算
// 先将数组 nums 所有数以及 1~N+2 区间所有数全部异或一遍，得到消失两数的异或
int ret = 0;
int a = 0;
int b = 0; // 分别表示两个消失的数
for(int i = 0; i < nums.size(); i++) {
ret ^= nums[i];
}
for(int i = 1; i <= nums.size() + 2; i++) {
ret ^= i;
}
// 此时 ret = a ^ b
// 由于 a 和 b 一定不同，所以一定会存在某一位比特位一个是 0 一个是 1
// 两者异或后对应的那一位就一定是 1，所以我们需要找到那一位
// 获取到 ret 最右侧出现 1 的比特位位置
int x = 0;
while(1) {
if(((ret >> x) & 1) == 1) {
break;
}
x++;
}
// 将数组 nums 所有数以及 (1~N+2) 区间所有数分成两类：
// 一类就是第 x 位比特位值为 0，一类就是第 x 位比特位值为 1
// 这样两个消失数就会被分开，通过异或，在数组以及 (1~N+2) 区间都出现的数就会抵消，
// a 和 b 也就分别是这两个消失数了
for(int i = 0; i < nums.size(); i++) {
if(((nums[i] >> x) & 1) == 0) // 假设 a 是第 x 位比特位为 0 的消失数
{
a ^= nums[i];
} else // 假设 b 就是第 x 位比特位为 1 的消失数
{
b ^= nums[i];
}
}
for(int i = 1; i <= nums.size() + 2; i++) {
if(((i >> x) & 1) == 0) {
a ^= i;
} else {
b ^= i;
}
}
// 两次循环则数组中存在的数异或了两次被抵消，a 和 b 就分别是两个消失数
return {a, b};
}
};
算法总结及流程解析
