知识点

十进制和二进制之间的相互转化

利用按位与操作符&可以实现

#include <bits/stdc++.h>

using namespace std;

int main(void){
    vector<int> t;
    int mask = 8;
    for(int i = 0; i <= 3; i ++){
        if(mask & (1 << i)){
            t.push_back(1);
        }else{
            t.push_back(0);
        }
    }

    for(int i = 3; i >= 0; i --){
        cout << t[i];
    }

    return 0;
}

子集

解题思路

我们可以发现，子集的表示可以转化为使用二进制表示
例如：n = 3, nums[] = [1, 2, 3]的子集可以用二进制数串表示

ID	二进制	子集
0	000	[]
1	001	[3]
2	010	[2]
3	011	[2, 3]
4	100	[1]
5	101	[1, 3]
6	110	[1, 2]
7	111	[1, 2, 3]

所以我们只需要枚举每种二进制表示，即可求得所有子集

实现代码

class Solution {
public:

    vector<int> t;
    vector<vector<int>> ans;



    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();

        for(int i = 0; i < (1 << n); i ++){
            t.clear();
            // 枚举所有二进制表示
            // 一共有2^n项
            for(int j = 0; j < n; j ++){
                if(i & (1 << j)){
                    // 用来找到二进制表示中“1”对应的数字
                    t.push_back(nums[j]);
                }
            }
            ans.push_back(t);
        }

        return ans;
    }
};

子集II

解题思路

题解做法

先对nums进行排序
首先还是按照题目子集进行查找
在查找过程中，如果发现前一个相同的数字没有参加到此子集的查找中，说明必定重复，可以中止当前搜索

我的做法

首先还是按照题目子集进行查找
但是由于数组中有重复的元素，我们在查找到所有子集后需要去重
- 当我们在寻找到一个子集后对其进行排序，这样保证了如果两个子集中的元素是相同的，我们通过去重模版可以将其删去
- 在返回ans前，对其进行去重
去重模版

sort(alls.begin(), alls.end())
alls.erase(unique(alls.begin(), alls.end()), alls.end());

实现代码

题解做法

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); i ++){
            t.clear();
            int flag = 1;
            for(int i = 0; i < n; i ++){
                if(mask & (1 << i)){
                    if(i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i - 1]){
                        // mask >> (i - 1) & 1 == 0
                        // 是用来判断有没有选择上一个数
                        // 这个顺序是从后往前来的
                        flag = false;
                        break;
                    }
                    t.push_back(nums[i]);
                }
                if(flag){
                    ans.push_back(t);
                }
            }
        }
    }
};

我的做法

class Solution {
public:
    vector<int> t;
    vector<vector<int>> ans;

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        int n = nums.size();

        for(int mask = 0; mask < (1 << n); mask ++){
            t.clear();
            for(int i = 0; i < n; i ++){
                if(mask & (1 << i)){
                    t.push_back(nums[i]);
                }
            }
            sort(t.begin(), t.end());
            ans.push_back(t);
        }

        sort(ans.begin(), ans.end());
        ans.erase(unique(ans.begin(), ans.end()), ans.end());
        return ans;
    }
};

子集 & 20250205每日一题

知识点

十进制和二进制之间的相互转化

子集

解题思路

实现代码

子集II

解题思路

题解做法

我的做法

实现代码

题解做法

我的做法

Enjoy Reading This Article?