欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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.算符优先级

>> 大于 &