难度: Medium
Submission
运行时间: 64 ms
内存: 25.9 MB
class Solution:
def subsequenceSumOr(self, nums: List[int]) -> int:
# cur, res, h, mask = 0, 0, max(nums).bit_length(), [1<<j for j in range(46)]
# for m in mask:
# for num in nums:
# if num&m: cur += 1
# if cur: res |= m
# cur >>= 1
# return res
if max(nums)==0: return 0
j, mask, ans = 0, reduce(ior,nums), (1<<sum(nums).bit_length())-1
while not mask&1:
ans ^= 1<<j
mask >>= 1
j += 1
return ans
Explain
此题解的核心思路是通过操作位来计算所有子序列的按位或的和。首先，利用Python内置的reduce函数和按位或操作ior，计算出给定数组nums中所有元素的按位或结果（变量mask）。然后，通过计算nums的所有元素之和的位长度，确定可能的最大位数，以此创建一个全1的掩码（变量ans）。接下来，从最低位开始，逐位检查mask的每一位，如果该位为0，则在ans对应的位上置0，以此去除不需要的最高位。最终，ans中剩下的即为所有子序列和的按位或结果。
时间复杂度: O(n + log C)
空间复杂度: O(1)
class Solution:
def subsequenceSumOr(self, nums: List[int]) -> int:
if max(nums) == 0: return 0 # 如果数组中最大值为0，直接返回0
j, mask, ans = 0, reduce(ior, nums), (1 << sum(nums).bit_length()) - 1 # 初始化变量：j为当前处理的位数，mask为所有数字的按位或结果，ans为初始掩码
while not mask & 1: # 循环直到mask的最低位为1
ans ^= 1 << j # 将结果ans的第j位翻转（即从1变为0）
mask >>= 1 # mask右移一位
j += 1 # 更新正在处理的位数
return ans # 返回最终计算的结果
Explore
`reduce`函数是一个高阶函数，它接收一个二元操作函数和一个序列，然后重复应用这个函数到序列的元素上，直到序列被归约为一个单一的值。在本题中，`reduce`使用`ior`函数作为操作函数。`ior`是`operator`模块中的函数，代表按位或操作。通过`reduce(ior, nums)`，我们可以连续对数组`nums`中的所有元素执行按位或操作，从而得到一个整数，这个整数的每一个位上的值表示该位在数组中至少有一个元素是1。这样，就能有效地计算出所有元素的按位或结果，这个结果是所有可能子序列按位或的上界。
在题解中使用`sum(nums).bit_length()`来确定掩码位数的原因是，这个值代表将数组中的所有元素相加后的和所需的最小位数。这是因为所有元素的总和代表了可能的最大数值范围，而其二进制位长度则反映了代表该数值所需的最大位数。通过创建一个全1的掩码，其位数等于`sum(nums)`的位长度，可以确保掩码足够大，能覆盖所有可能的按位或结果。这种方法确保了在后续的操作中不会因位数不足而丢失重要信息。
检查`max(nums) == 0`并直接返回0的逻辑基于按位或运算的特性。按位或运算的结果中的每一位都是对应位上至少有一个1时该位才为1。如果数组中的最大值是0，意味着数组中的所有元素都是0，因此任何子序列的按位或结果也将是0。因为在所有元素都是0的情况下，无论组合多少个0，其按位或的结果仍然是0。这个检查是一个优化步骤，可以在明确结果为0的情况下避免不必要的计算。