vegatable

0%

Bitwise ORs of Subarrays

发表于 阅读次数： Valine：
本文字数： 1.2k 阅读时长 ≈ 2 分钟

LeetCode 898. Bitwise ORs of Subarrays

Desc:

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

$$
0 \le a[i] \le 10^9
$$

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去重和插入的时间

大概复杂度是
$$
log(10^9)N=30N
$$
然后 然后我冲了 （反正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();
    }
};