5

力扣每日一题——统计按位或能得到最大值的子集数目

 3 years ago
source link: https://unique-pure.github.io/2022/03/14/suan-fa-xue-xi-ji-hua/mei-ri-yi-ti/20220315/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

1 题目描述

image-20220315143903655
image-20220315143903655

2 位运算 O(n×2n)O(n×2n)

对于每个元素可以选取或者不选取，我们就可以用一个长度为n比特的整数来表示不同的子集，其中第i位的值就表示是否选取。根据这个值我们求出每个子集的按位或的值，并计算最优解。

class Solution {
public:
    int countMaxOrSubsets(vector<int>& nums) {
        int n = nums.size();
        int res = 0, maxx = 0, ans = 1 << n;
        for (int mask = 0; mask < ans; mask ++ ) {
            int cur = 0;
            for (int i = 0; i < n; ++ i ) {
                if (((mask >> i) & 1) == 1) {
                    cur |= nums[i];
                }
            }
            if (cur == maxx) {
                ++ res;
            } else if (cur > maxx) {
                maxx = cur;
                res = 1;
            }
        }
        return res;
    }
};

3 递归 O(2n)O(2n)

通过递归构造这2n−12n−1个子集即可。

class Solution {
private:
    int res, maxx, n;
public:
    int countMaxOrSubsets(vector<int>& nums) {
        n = nums.size();
        maxx = 0, res = 0;
        dfs(nums, 0, 0);
        return res;
    }
    void dfs(vector<int>& nums, int idx, int score) {
        if (idx >= n) {
            if (score == maxx) {
                ++ res;
            } else if (score > maxx) {
                maxx = score;
                res = 1;
            }
            return;
        }
        dfs(nums, idx + 1, score | nums[idx]);
        dfs(nums, idx + 1, score);
    }
};

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK