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

标签: 位运算 数组 回溯

难度: Medium

给你一个整数数组 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

Submission

运行时间: 40 ms

内存: 16.2 MB

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        xor_sum = reduce(or_, nums)
        c = Counter()  # 记录前面所有子集的按位或的结果
        for x in nums:
            items = list(c.items())
            for k, v in items:
                c[k|x] += v
            c[x] += 1
        return c[xor_sum]

Explain

这个题解的核心思路是使用动态规划的方式来解决问题。首先，通过对数组中所有元素进行按位或操作，计算出能够得到的最大值 xor_sum。接着，使用一个字典 c 来保存不同子集按位或结果的出现次数。遍历每个元素 x，将已经存在的按位或结果与新元素 x 进行按位或操作，并更新这些结果的计数。特别地，每个元素自身也被视为一个子集，因此每次遍历到新元素时，都将其按位或结果计数增加1。最后，返回字典 c 中按位或结果为 xor_sum 的子集数量。

时间复杂度: O(n * 2^17 * log(n))

空间复杂度: O(2^17)

from functools import reduce
from operator import or_
from collections import Counter

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        # 计算所有元素的按位或结果，得到最大值
        xor_sum = reduce(or_, nums)
        # 使用 Counter 来记录每个按位或结果的出现次数
        c = Counter()
        for x in nums:
            # 复制当前字典以避免在迭代过程中修改字典
            items = list(c.items())
            for k, v in items:
                # 更新字典中的按位或结果的计数
                c[k|x] += v
            # 每个元素自身也视为一个子集
            c[x] += 1
        # 返回最大按位或结果的子集数量
        return c[xor_sum]

Explore

按位或操作具有累积性和非减性质，这意味着对任意整数进行按位或操作的结果只会增加或保持不变，不会减少。因此，在给定一组数时，对它们全部进行按位或操作，可以确保得到这组数能达到的最大按位或值。这是因为任何子集的按位或结果都不会超过全集的按位或结果。所以，通过reduce函数结合or_操作符逐个合并数组中的所有元素能准确无误地得到最大按位或值。

在这个问题中，动态规划的状态可以定义为在考虑到当前元素之前，每一个可能的按位或结果及其出现的次数。状态转移则是基于新加入的元素更新这些按位或结果。具体来说，对于每一个新元素x，我们考虑已有的所有按位或结果（由Counter字典c维护），将x与这些结果进行按位或操作，并更新这些新结果的计数。此外，元素x本身也被添加到字典中，作为新的结果。

在Python中，字典在迭代时不能修改（增加或删除键值对），因为这会影响迭代器的状态，可能导致运行时错误或不正确的行为。在本题解中，我们需要在迭代过程中基于当前按位或的结果生成新的结果并更新这些结果的计数。如果不复制当前字典，那么在迭代字典的同时修改字典（如添加新的按位或结果），将引发运行时错误。通过先复制字典项为列表，我们可以在遍历这个列表的同时，安全地修改原字典。

在代码实现中，如果字典c中不存在xor_sum，表示没有任何子集的按位或结果等于xor_sum。这种情况理论上不会发生，因为xor_sum是从所有元素的按位或中得到的最大值。但为了代码的健壮性，可以通过字典的get方法访问xor_sum的计数，如果不存在，则默认返回0。即，使用c.get(xor_sum, 0)可以安全地处理这种异常情况，确保总是返回一个整数结果。