Skip to content

Latest commit

 

History

History
132 lines (79 loc) · 4.08 KB

898.bitwise-ors-of-subarrays.md

File metadata and controls

132 lines (79 loc) · 4.08 KB

题目地址(898. 子数组按位或操作)

https://leetcode-cn.com/problems/bitwise-ors-of-subarrays/

题目描述

我们有一个非负整数数组 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

前置知识

公司

  • 暂无

思路

我们首先需要对问题进行分解,分解的思路和 【西法带你学算法】一次搞定前缀和 中提到的一样。这里简单介绍一下,如果还不明白的,建议看下那篇文章。

题目需要求的是所有子数组或运算后的结果的数目(去重)。一个朴素的思路是求出所有的子数组,然后对其求或,然后放到 hashset 中去重,最后返回 hashset 的大小即可。

我们可以使用固定两个端点的方式在 $O(n^2)$ 的时间计算出所有的子数组,并在 $O(n)$ 的时间求或,因此这种朴素的算法的时间复杂度是 $O(n^2 + n)$

要点 1

而由于子数组具有连续性,也就是说如果子数组 A[i:j] 的或是 OR(i,j)。那么子数组 A[i:j+1] 的或就是 OR(i,j) | A[j+1],也就是说,我们无需重复计算 OR(i, j)。基于这种思路,我们可以写出 $O(n)$ 的代码。

要点 2

所有的子数组其实就是:

  • 以索引为 0 结束的子数组
  • 以索引为 1 结束的子数组
  • 。。。

因此,我们可以边遍历边计算,并使用上面提到的技巧,用之前计算的结果推导下一步的结果。

算法(假设当前遍历到了索引 i):

  • 用 pres 记录上一步的子数组异或值集合,也就是以索引 i - 1 结尾的子数组异或值集合
  • 遍历 pres,使用 pres 中的每一项和当前数进行或运算,并将结果重新放入 pres。最后别忘了把自身也放进去。

为了防止迭代 pres 过程改变 pres 的值,我们可以用另外一个中间临时集合承载结果。

  • 将 pres 中的所有数加入 ans,其中 ans 为我们要返回的一个 hashset

关键点

  • 子数组是连续的,有很多性质可以利用

代码

  • 语言支持:Python3

Python3 Code:

class Solution(object):
    def subarrayBitwiseORs(self, A):
        pres = set([0])
        ans = set()
        for a in A:
            nxt = set()
            for pre in pres:
                nxt.add(a | pre)
                nxt.add(a)
            pres = nxt
            ans |= nxt
        return len(ans)

复杂度分析

令 n 为数组长度。

  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(n)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。