Bitwise ORs of Subarrays

LeetCode 898. Bitwise ORs of Subarrays

Desc:

有一个非负整数数组a,对所有整数对(i,j)求 a[i]|a[i+1]|a[i+2]…a[j] 的值(|为按位或),求共有多少个不相等的值

My_Ans:

n^2裸题 冲冲冲

设b(i,j)=a[i]|a[i+1]….|a[j] 用一个set now保存b(0,i),b(1,i),b(2,i)

然后每次处理到a[i+1]的时候 把now里的所有项和a[i+1] 按位或一下

然后把a[i+1]添加到now里

但是这个范围好像给我喂了一口X….

仔细分析 10^9 那好像最多也不会有很多数啊

按位或的特性就是一旦有了1就不会再变成0了…

那也就是说最坏的情况下now这个集合里只会有30个不同的值

但是这个过程中我们会遇到一个巨大的数据结构常数 即set去重和插入的时间

大概复杂度是

然后 然后我冲了 (反正leetcode 复杂度这么宽

莽夫是这样的

UPD: 再思考一下你会发现b(i,j)可以从b(i+1,j)推出来可以少一个set now 貌似能跑更快

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int subarrayBitwiseORs(vector<int> A) {
unordered_set<int> result, now, tmp;
for (auto i: A) {
tmp = {i};
for (auto j: now) tmp.insert(i|j);
now = tmp;
for (auto j: now) result.insert(j);
}
return result.size();
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int subarrayBitwiseORs(vector<int>& A) {
int maxval = *max_element(A.begin(), A.end()),mask=1;
while (maxval >= mask) mask <<= 1;
mask -= 1;
if (mask == 0) return 1;
unordered_set<int> nums;
for (int i = 0; i < A.size(); ++i) {
int val = 0;
for (int j = i; j >= 0 && val != mask; --j) {
val |= A[j];
nums.insert(val);
}
}
return nums.size();
}
};