目录
位运算
1. 136. 只出现一次的数字
2. 338. 比特位计数
3. 461. 汉明距离
位运算
1. 136. 只出现一次的数字
简单
给你一个 非空 整数数组 nums
,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。
示例 1 :
输入:nums = [2,2,1] 输出:1
示例 2 :
输入:nums = [4,1,2,1,2] 输出:4
示例 3 :
输入:nums = [1] 输出:1
提示:
1 <= nums.length <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
- 除了某个元素只出现一次以外,其余每个元素均出现两次。
class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_map<int, int> count; // 创建一个哈希表来计数// 遍历数组,统计每个数字的出现次数
for (int i = 0; i < nums.size(); i++) {
count[nums[i]]++;
}// 查找唯一出现一次的数字
for (int i = 0; i < nums.size(); i++) {
if (count[nums[i]] == 1) {
return nums[i]; // 返回该数字
}
}return 0; // 如果没有找到,返回0
}
};
解释:
// 位运算
// 异或运算的性质
// 1.任何数和0做异或运算,结果仍是原来的数
// 2.任何数和自己异或结果是0
// 3.异或运算满足交换律和结合律
2. 338. 比特位计数
简单
给你一个整数 n
,对于 0 <= i <= n
中的每个 i
,计算其二进制表示中 1
的个数 ,返回一个长度为 n + 1
的数组 ans
作为答案。
示例 1:
输入:n = 2 输出:[0,1,1] 解释: 0 --> 0 1 --> 1 2 --> 10
示例 2:
输入:n = 5 输出:[0,1,1,2,1,2] 解释: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101
提示:
0 <= n <= 105
// 位运算
class Solution {
public:
vector<int> countBits(int n) {
vector<int> result; // 用于存储每个数字的位1个数
// 遍历从 0 到 n 的每个数字
for (int i = 0; i <= n; ++i) {
int count = 0; // 计数器,初始化为 0
int num = i; // 复制当前数字
// 计算 num 的位1的个数
while (num > 0) {
if (num & 1) { // 检查最低位是否为1
++count; // 如果是1,则计数器加1
}
num = num >> 1; // 右移一位,处理下一个位
}
result.push_back(count); // 将计数结果添加到结果向量中
}
return result; // 返回包含每个数字位1个数的向量
}
};
3. 461. 汉明距离
简单
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x
和 y
,计算并返回它们之间的汉明距离。
示例 1:
输入:x = 1, y = 4 输出:2 解释: 1 (0 0 0 1) 4 (0 1 0 0)↑ ↑ 上面的箭头指出了对应二进制位不同的位置。
示例 2:
输入:x = 3, y = 1 输出:1
提示:
0 <= x, y <= 231 - 1
// 方法1. 内置位计数功能
class Solution {
public:
int hammingDistance(int x, int y) {
// 计算 x 和 y 的异或结果,然后使用内置函数 __builtin_popcount 统计结果中 1 的个数
return __builtin_popcount(x ^ y);
}
};// 位运算
//方法 2. 移位实现位计数
class Solution {
public:
int hammingDistance(int x, int y) {
int s = x ^ y; // 计算 x 和 y 的异或,得到不同位的结果
int ret = 0; // 初始化计数器,用于记录不同位的个数// 逐位检查异或结果,统计其中的 1 的个数
while (s) {
ret += s & 1; // 检查最低位是否为 1,若是,则计数加 1
s >>= 1; // 将 s 右移一位,处理下一个位
}return ret; // 返回不同位的总数(汉明距离)
}
};
解释:
x ^ y
是位运算中的异或操作。它的结果是将 x
和 y
的每一位进行比较,若对应的两位相同则结果为 0
,若不同则结果为 1
。例如:x=5,y=3,则x ^ y结果如下:
0101 (5)
^ 0011 (3)
--------
0110 (6)