898_medium_子数组按位或操作.md

Leetcode 898 子数组按位或操作

---

题目描述

我们有一个非负整数数组 A。

对于每个（连续的）子数组 B = [A[i], A[i+1], ..., A[j]] （ i <= j），我们对 B 中的每个元素进行按位或操作，获得结果 A[i] | A[i+1] | ... | A[j]。

返回可能结果的数量。 （多次出现的结果在最终答案中仅计算一次。）

示例1:

输入：[0]
输出：1
解释：
只有一个可能的结果 0 。

示例2:

输入：[1,1,2]
输出：3
解释：
可能的子数组为 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。
产生的结果为 1，1，2，1，3，3 。
有三个唯一值，所以答案是 3 。

示例3:

输入：[1,2,4]
输出：6
解释：
可能的结果是 1，2，3，4，6，以及 7 。

提示：

1. 1 <= A.length <= 50000
2. 0 <= A[i] <= 10^9

考点

• 位操作、动态规划？？

思路

评论说，动态规划时间复杂度很高。直接利用python的集合操作更快更直接。
cur集合存放当前集合与新加进来的元素或操作结果，然后跟res集合或操作合并到res集合中。

代码

执行用时: 736ms, 内存消耗: 39.2MB。

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        cur, res = set(), set()
        for a in A:
            cur = {a | b for b in cur}
            cur.add(a)
            res |= cur
        return len(res)