0898. Bitwise O Rs of Subarrays

898. Bitwise ORs of Subarrays#

题目 #

We have an array `A` of non-negative integers.

For every (contiguous) subarray `B = [A[i], A[i+1], ..., A[j]]` (with `i <= j`), we take the bitwise OR of all the elements in `B`, obtaining a result `A[i] | A[i+1] | ... | A[j]`.

Return the number of possible results. (Results that occur more than once are only counted once in the final answer.)

Example 1:

``````Input: [0]
Output: 1
Explanation:
There is only one possible result: 0.
``````

Example 2:

``````Input: [1,1,2]
Output: 3
Explanation:
The possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2].
These yield the results 1, 1, 2, 1, 3, 3.
There are 3 unique values, so the answer is 3.
``````

Example 3:

``````Input: [1,2,4]
Output: 6
Explanation:
The possible results are 1, 2, 3, 4, 6, and 7.
``````

Note:

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

解题思路 #

• 给出一个数组，要求求出这个数组所有的子数组中，每个集合内所有数字取 `|` 运算以后，不同结果的种类数。
• 这道题可以这样考虑，第一步，先考虑所有的子数组如何得到，以 `[001, 011, 100, 110, 101]` 为例，所有的子数组集合如下：
``````    [001]
[001 011] [011]
[001 011 100] [011 100] [100]
[001 011 100 110] [011 100 110] [100 110] [110]
[001 011 100 110 101] [011 100 110 101] [100 110 101] [110 101] [101]
``````

• 第二步，将每一行的子集内的所有元素都进行 `|` 运算，得到：
``````    001
011 011
111 111 100
111 111 110 110
111 111 111 111 101
``````
• 第三步，去重：
``````    001
011
111 100
111 110
111 101
``````

代码 #

``````
package leetcode

// 解法一 array 优化版
func subarrayBitwiseORs(A []int) int {
res, cur, isInMap := []int{}, []int{}, make(map[int]bool)
cur = append(cur, 0)
for _, v := range A {
var cur2 []int
for _, vv := range cur {
tmp := v | vv
if !inSlice(cur2, tmp) {
cur2 = append(cur2, tmp)
}
}
if !inSlice(cur2, v) {
cur2 = append(cur2, v)
}
cur = cur2
for _, vv := range cur {
if _, ok := isInMap[vv]; !ok {
isInMap[vv] = true
res = append(res, vv)
}
}
}
return len(res)
}

func inSlice(A []int, T int) bool {
for _, v := range A {
if v == T {
return true
}
}
return false
}

// 解法二 map 版
func subarrayBitwiseORs1(A []int) int {
res, t := map[int]bool{}, map[int]bool{}
for _, num := range A {
r := map[int]bool{}
r[num] = true
for n := range t {
r[(num | n)] = true
}
t = r
for n := range t {
res[n] = true
}
}
return len(res)
}

``````

Apr 8, 2023