### 题目描述 给你一个整数数组 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 ### 题目解答 根据题目所给的数组长度范围，也可以看到可以采用回溯法，在dfs的过程中，选定1位或者不选定1位。在dfs罗列的过程中，不断更新记录最大值即可。 **算法复杂度分析** 假设数组长度为n 时间复杂度：共罗列2的n次方种情况，O(n^2) 空间复杂度：开栈深度最大为O(n) #### 代码实现 ```python class Solution: def __init__(self): self.res = 0 self.max_num = 0 def countMaxOrSubsets(self, nums: List[int]) -> int: def dfs(nums, index, now_value): if index == len(nums): return # 不选择这个数字 dfs(nums, index+1, now_value) # 选定这个数字 now_value |= nums[index] if now_value == self.max_num: self.res += 1 dfs(nums, index+1, now_value) for num in nums: self.max_num |= num dfs(nums, 0, 0) return self.res ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复