LeetCode1863:找出所有子集的异或总和再求和
一、题目描述
二、示例
三、条件限制
四、解题思路及代码
4.1 枚举子集
比较常见的思路是先枚举出列表的所有子集,然后对每个子集的元素求异或,最后累加各异或值。
下面是Python生成列表所有子集的一般方法:
1 | def combination(nums): |
不过我们可以通过itertools模块中的combinations快速生成子集,函数如下:
1 | combinations(iterable, r) # 参数1是可迭代对象,参数2是子集的元素数量 |
该题该方案完整代码如下:
1 | from itertools import combinations |
4.2 进制位法
一个长度为 $n$ 的数组 $nums$ 有 $2^n$ 个子集(包括空集与自身),数组中的每个元素都有「选取」与「未选取」两个状态,可以对应一个二进制位的 1 与 0。那么对于一个长度为 $n$ 的数组 $nums$ ,我们可以用 $n$ 个二进制位表示每个元素的选取情况,此时该二进制数第 $j$ 位的取值表示数组第 $j$ 个元素是否包含在对应的子集中。那么,每个子集就可转化为一串二进制数,即我们可以将这些子集一一映射到 $[0, 2^n -1]$ 中的整数。
因此,我们遍历 $[0, 2^n -1]$ 中的整数,每个整数实则代表了一种子集情况,遍历它的每一位计算对应子集的异或总和,并维护这些值之和。
1 | class Solution: |
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 | class Solution: |