张家港杨舍网站建设,信息化设计公司排名,徐州网络推广服务,网站项目宣传片文章目录1. 题目2. 解题1. 题目
给你一个整数数组 nums #xff0c;请你找出 nums 子集 按位或 可能得到的 最大值 #xff0c;并返回按位或能得到最大值的 不同非空子集的数目 。
如果数组 a 可以由数组 b 删除一些元素#xff08;或不删除#xff09;得到#xff0c;则…
文章目录1. 题目2. 解题1. 题目
给你一个整数数组 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] 10^5来源力扣LeetCode 链接https://leetcode-cn.com/problems/count-number-of-maximum-bitwise-or-subsets 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
状态压缩DP
class Solution {
public:int countMaxOrSubsets(vectorint nums) {int n nums.size();vectorint dp(1n);for(int i 0; i n; i)dp[1i] nums[i];int ans 0;for(int state 1; state (1n); state){int prevState state(state-1);dp[state] dp[prevState] | dp[state-prevState];ans max(ans, dp[state]);}int ct 0;for(int state 1; state (1n); state){if(dp[state] ans)ct;}return ct;}
};32 ms 15.4 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
