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

一、题目描述

二、示例

三、条件限制

四、解题思路及代码

4.1 枚举子集

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

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

1
2
3
4
5
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是子集的元素数量

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

1
2
3
4
5
6
7
8
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]\) 中的整数,每个整数实则代表了一种子集情况,遍历它的每一位计算对应子集的异或总和,并维护这些值之和。

1
2
3
4
5
6
7
8
9
10
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\) 的情况)

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