第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0898. 子数组按位或操作

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

题目描述

1
我们有一个非负整数数组 A。
2
3
对于每个(连续的)子数组 B = [A[i], A[i+1], ..., A[j]] ( i <= j),我们对 B 中的每个元素进行按位或操作,获得结果 A[i] | A[i+1] | ... | A[j]。
4
5
返回可能结果的数量。 (多次出现的结果在最终答案中仅计算一次。)
6
7
8
9
示例 1:
10
11
输入:[0]
12
输出:1
13
解释:
14
只有一个可能的结果 0 。
15
16
17
示例 2:
18
19
输入:[1,1,2]
20
输出:3
21
解释:
22
可能的子数组为 [1],[1],[2],[1, 1],[1, 2],[1, 1, 2]。
23
产生的结果为 1,1,2,1,3,3 。
24
有三个唯一值,所以答案是 3 。
25
26
27
示例 3:
28
29
输入:[1,2,4]
30
输出:6
31
解释:
32
可能的结果是 1,2,3,4,6,以及 7 。
33
34
35
36
37
提示:
38
39
1 <= A.length <= 50000
40
0 <= A[i] <= 10^9
Copied!

前置知识

公司

  • 暂无

思路

我们首先需要对问题进行分解,分解的思路和 【西法带你学算法】一次搞定前缀和 中提到的一样。这里简单介绍一下,如果还不明白的,建议看下那篇文章。
题目需要求的是所有子数组或运算后的结果的数目(去重)。一个朴素的思路是求出所有的子数组,然后对其求或,然后放到 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:
1
class Solution(object):
2
def subarrayBitwiseORs(self, A):
3
pres = set([0])
4
ans = set()
5
for a in A:
6
nxt = set()
7
for pre in pres:
8
nxt.add(a | pre)
9
nxt.add(a)
10
pres = nxt
11
ans |= nxt
12
return len(ans)
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(n)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。