跳转至

LeetCode: 898. 子数组按位或操作

1、题目描述

我们有一个非负整数数组 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 <= A.length <= 50000
  • 0 <= A[i] <= 10^9

2、解题思路

  • 如果使用暴力法,时间复杂度为O(N^2)
  • 由于或运算的特殊性,从前面向后进行位或,只会将某一位进行置一,因此从某一位看,当前为作为截止位产生多少不同的数字,由于数字最大为10^9,因此以当前数字为截止的连续子数组产生的数字最多32个
  • 因此,只需要统计从前面到后面,到当前位置截止产生的所有的数字加入结果集中即可
class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        res = set(A)
        current = set()

        for i in A:
            current = {i | x for x in current} | {i}
            res |= current
        return len(res)