LeetCode 由子集问题联想到的关于解决排列组合问题的位运算方法
程序员文章站
2022-07-14 16:15:43
...
子集:https://leetcode-cn.com/problems/subsets/
子集Ⅱ:https://leetcode-cn.com/problems/subsets-ii/
下面直接由代码代入,注释解释问题:
算法概述:
1.数组排序
2.若发现没有选择上一个数,且当前数字与上一个数相同,则跳过
class Solution {
public:
vector<int> t;
vector<vector<int>> ans;
vector<vector<int>> subsetsWithDup(vector<int> &nums) {
sort(nums.begin(), nums.end()); //标准库排序
int n = nums.size();
for (int mask = 0; mask < (1 << n); ++mask) { //利用mask二进制位实现选中那些数
t.clear();
bool flag = true;
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) { //判断第i位是不是mask中选中的位
if (i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i - 1]) { //第二个是判断i-1位的mask是不是为1
flag = false;
break;
}
t.push_back(nums[i]);
}
}
if (flag) {
ans.push_back(t);
}
}
return ans;
}
};
总结:
1.在类似多个位中随机选几位可使用位运算
如 1 1 两位,循环从0~3则可实现,00 01 10 11
2.移位操作可得到某个位
如: (011>>1)&1 可得到第2位的值
3.算符优先级
>> 大于 &
下一篇: Thread.sleep()方法