LeetCode-2044 统计按位或能得到最大值子集的数目

简介: LeetCode-2044 统计按位或能得到最大值子集的数目

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/count-number-of-maximum-bitwise-or-subsets

题目描述

给你一个整数数组 nums ,请你找出 nums 子集 按位或 可能得到的 最大值 ,并返回按位或能得到最大值的 不同非空子集的数目 。

如果数组 a 可以由数组 b 删除一些元素(或不删除)得到,则认为数组 a 是数组 b 的一个 子集 。如果选中的元素下标位置不一样,则认为两个子集 不同 。

对数组 a 执行 按位或 ,结果等于 a[0] OR a[1] OR ... OR a[a.length - 1](下标从 0 开始)。

 

示例 1:

输入:nums = [3,1]

输出:2

解释:子集按位或能得到的最大值是 3 。有 2 个子集按位或可以得到 3 :

- [3]

- [3,1]

示例 2:

输入:nums = [2,2,2]

输出:7

解释:[2,2,2] 的所有非空子集的按位或都可以得到 2 。总共有 23 - 1 = 7 个子集。

示例 3:

输入:nums = [3,2,1,5]

输出:6

解释:子集按位或可能的最大值是 7 。有 6 个子集按位或可以得到 7 :

- [3,5]

- [3,1,5]

- [3,2,5]

- [3,2,1,5]

- [2,5]

- [2,1,5]

 

提示:

1 <= nums.length <= 16

1 <= nums[i] <= 105

 

解题思路

观察数组最大规模仅仅16,直接使用暴力dfs枚举所有子集求得最大子集并统计数目。

代码展示

 

class Solution {
public:
    int miRet = 0;
    int miMax = 0;
    void dfs(int index, vector<int>& nums, int sum)
    {
        if(index == nums.size())
        {
            if(sum > miMax)
            {
                miRet = 1;
                miMax = sum;
            }
            else if(sum == miMax)
            {
                miRet++;
            }
        }
        else
        {
            dfs(index + 1, nums, sum);
            dfs(index + 1, nums, sum | nums[index]);
        }
    }
    int countMaxOrSubsets(vector<int>& nums) {
        dfs(0, nums, 0);
        return miRet;
    }
};

运行结果

 

相关文章
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
算法
LeetCode第90题子集II
LeetCode第90题"子集II"的解题方法,通过排序和回溯算法生成所有不重复的子集,并使用一个boolean数组来避免同一层中的重复元素,展示了解决这类问题的编码技巧。
LeetCode第90题子集II
|
4月前
|
Python
【Leetcode刷题Python】416. 分割等和子集
LeetCode 416题 "分割等和子集" 的Python解决方案,使用动态规划算法判断是否可以将数组分割成两个元素和相等的子集。
33 1
|
4月前
|
索引 Python
【Leetcode刷题Python】78. 子集
LeetCode题目78的Python编程解决方案,题目要求给定一个互不相同的整数数组,返回该数组所有可能的子集(幂集),且解集中不能包含重复的子集。
25 1
|
4月前
|
算法
LeetCode第78题子集
文章分享了LeetCode第78题"子集"的解法,使用递归和回溯算法遍历所有可能的子集,展示了将子集问题视为树形结构进行遍历的解题技巧。
|
4月前
|
存储 算法 Java
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
46 0
|
5月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
5月前
2670.找出不同元素数目差数组-力扣(LeetCode)
2670.找出不同元素数目差数组-力扣(LeetCode)
34 0
|
6月前
|
机器学习/深度学习 存储 算法
LeetCode题目 90:五种算法 回溯\迭代\位掩码\字典树\动态规划实现 子集ll
LeetCode题目 90:五种算法 回溯\迭代\位掩码\字典树\动态规划实现 子集ll
|
6月前
|
存储 机器学习/深度学习 算法
力扣78题:生成子集
力扣78题:生成子集