LeetCode1863:找出所有子集的异或总和再求和

2021-07-27 阅读量:

一、题目描述

二、示例

三、条件限制

四、解题思路及代码

4.1 枚举子集

比较常见的思路是先枚举出列表的所有子集，然后对每个子集的元素求异或，最后累加各异或值。

下面是Python生成列表所有子集的一般方法：

def combination(nums):
    ans = [[]] # 含空集的初始列表
    for num in nums:
        ans.extend([x+[num] for x in ans])
    return ans

不过我们可以通过itertools模块中的combinations快速生成子集，函数如下：

1	combinations(iterable, r) # 参数1是可迭代对象，参数2是子集的元素数量

该题该方案完整代码如下：

from itertools import combinations
class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        ans = [combinations(nums, i+1) for i in range(len(nums))]
        ss = 0
        for i in ans:
            ss += sum([reduce(lambda x,y:x^y, lst) for lst in i])
        return ss

4.2 进制位法

一个长度为 $n$ 的数组 $nums$ 有 $2^n$ 个子集（包括空集与自身），数组中的每个元素都有「选取」与「未选取」两个状态，可以对应一个二进制位的 1 与 0。那么对于一个长度为 $n$ 的数组 $nums$ ，我们可以用 $n$ 个二进制位表示每个元素的选取情况，此时该二进制数第 $j$ 位的取值表示数组第 $j$ 个元素是否包含在对应的子集中。那么，每个子集就可转化为一串二进制数，即我们可以将这些子集一一映射到 $[0, 2^n -1]$ 中的整数。

因此，我们遍历 $[0, 2^n -1]$ 中的整数，每个整数实则代表了一种子集情况，遍历它的每一位计算对应子集的异或总和，并维护这些值之和。

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        res = 0
        for integer in range(1 << len(nums)):
            ans = 0
            for j in range(len(nums)):
                if integer & (1 << j): # 判断二进制串上该位是否为1
                    ans ^= nums[j]
            res += ans
        return res

4.3 按位考虑 + 二项式展开

假设初始数组大小为 $N$，数组中每个元素均可用定长的二进制数表示。设数组所有元素中第 $i$ 位为 $1$ 的元素个数为 $K$，则第 $i$ 位为 $0$ 的元素个数为 $N-K$。对于某个子集，只有当该子集中第 $i$ 位为 $1$ 的元素个数总数为奇数时，子集元素最终异或结果的第 $i$ 位方为 $1$，那么只要我们求出这样的子集的总数目 $Count$ ，就可得出第 $i$ 位对最终结果影响为 $Count * (1 << i)$ 。而 $Count$ 的计算包括从第 $i$ 位为 $1$ 的 $K$ 个元素中选择奇数个和从第 $i$ 位为 $0$ 的 $N-K$ 个元素中任意选两个阶段，所以：

$Count=(C_K^1+C_K^3+C_K^5+\dots+C_K^m)*2^{N-K}$

其中 $m$ 为不大于 $K$ 的最大奇数。

而二项式系数，奇数项之和 = 偶数项之和 = $2^{K-1}$ 。

故：

$Count = 2^{K-1}*2^{N-K} = 2^{N-1}$

所以第 $i$ 位对结果的影响为： $2^{N-1}*(1 << i)$。此结果与 $K$ 无关，因此我们只需对所有元素求或再移位即可。（排除数组中所有元素对应二进制数某位上全为 $0$ 的情况）

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        ans = 0
        for num in nums:
            ans |= num
        return ans << (len(nums)-1)