位运算：其他
睡不醒的鲤鱼 2021-05-15 每日一题 LeetCode
# 0078. 子集 (opens new window)
题目
给你一个整数数组 nums，数组中的元素互不相同，返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集，你可以按任意顺序返回解集。
由于一个长度为 n 的 nums 数组，其子集个数为 ，可以用一个二进制串表示每个元素是否出现，依此构建子集。
代码
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> ans;
for (int mask = 0; mask < (1 << n); mask++) {
vector<int> subset;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) subset.push_back(nums[i]);
}
ans.push_back(subset);
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 0137. 只出现一次的数字 II (opens new window)
题目
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
统计所有数字每一位中 1 的数量，如果可以整除 3，说明结果这一位为 0，否则为 1。
代码
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for (int i = 0; i < 32; i++) {
int cnt = 0;
for (auto &num: nums) {
cnt += (num >> i) & 1;
}
if (cnt % 3) ans |= (1 << i);
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 0397. 整数替换 (opens new window)
题目
给定一个正整数 n ，你可以做如下操作：
如果 n 是偶数，则用 n / 2替换 n 。 如果 n 是奇数，则可以用 n + 1 或 n - 1 替换 n 。 n 变为 1 所需的最小替换次数是多少？
解析
当 n 为奇数时：
- 如果倒数第二位是 0，那么 n - 1 操作能消掉更多的 1；
- 1001 + 1 = 1010
- 1001 - 1 = 1000
- 如果倒数第二位是 1，那么 n + 1 操作能消掉更多的 1；
- 1011 + 1 = 1100
- 1111 + 1 = 10000
注意
- 为了防止越界，需要将 n 转化为长整型计算；
- 当 n 为 3 时需要进行 n - 1 操作，不满足上面规律，需要特殊讨论。
代码
class Solution {
public:
int integerReplacement(int n) {
long nl = n;
int ans = 0;
while (nl != 1) {
if ((nl & 1) == 0) { // n 为偶数
nl >>= 1;
} else if (nl == 3) { // 特殊处理 3
nl--;
} else { // n 为奇数，判断后两位
nl = (nl & 2) == 2 ? nl + 1 : nl - 1;
}
ans ++;
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Login to view comments