209 小R的子数组权值

题解

题目描述

小 R 有一个长度为 n 的数组 a，她定义每个子区间 [l, r] 的权值为 a[l] | a[l+1] | ... | a[r]，即该区间内所有元素的按位或运算结果。小 R 非常好奇，在这 n × (n + 1) / 2 个子区间中，究竟有多少种不同的权值。

解题思路

对于两个二进制数 a 和 b，如果满足 a & b = a，从集合的角度来看，a 对应的集合是 b 对应集合的子集。

遍历数组：仍然从左到右遍历数组 a，对于当前元素 x = a[i]。
反向遍历更新：从索引 i-1 开始，向前遍历 a[j]：
- 检查子集关系：
  - 如果 a[j] & x != a[j]，说明 a[j] 可以通过与 x 进行按位与运算而变小（即集合元素减少）。此时，更新 a[j] = a[j] & x，并将更新后的值加入结果集合 res 中。
  - 如果 a[j] & x == a[j]，则 x 是 a[j] 的超集。同时，由于之前的遍历已经保证了每个集合都是其左侧相邻集合的超集，x 也必然是所有左侧集合的超集。在这种情况下，进一步的遍历将不会导致任何集合的变化，因此可以直接退出内层循环，提高算法效率。

代码实现



def solution(a):
    res = set()
    for i, x in enumerate(a):
        res.add(x)
        j = i - 1
        while j >= 0 and a[j] | x != a[j]:
            a[j] |= x
            res.add(a[j])
            j -= 1

    return len(res)

if __name__ == '__main__':
    print(solution([1, 2, 4]) == 6)
    print(solution([5, 3, 8, 1]) == 8)
    print(solution([1, 1]) == 1)
    print(solution([7, 8, 9, 10, 11]) == 6)