[LeetCode] 898. Bitwise ORs of Subarrays

[grandyang]

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

这是一道蛮有意思的题目，说是给了一个数组，里面都是非负数，问我们所有连续的子数组'或'起来能产生多少个不同的值。虽说这只是一道 Medium 的题，但是直觉告诉博主，暴力遍历所有子数组，并且一个一个的'或'将会产生大量的重复运算，不出意外应该是会 TLE 的。所以博主的第一直觉是能不能建立类似累加和一样的数组，然后快速计算任意区间的总'或'值，尝试了一下，虽然可以建立累加'或'数组，但是无法得到正确的区间总'或'值，博主甚至尝试了'异或'，仍然不对，只得作罢。其实这道题的正确解法还是蛮巧妙的，感觉不容易一下子想到，这里主要参考了 网上大神 zhoubowei 的帖子，举个例子吧，比如数组 [0, 3, 4, 6, 5]，写成二进制的就是 [000, 011, 100, 110, 101]，生成子数组的方法跟生成子集合 Subsets 有些类似，两者的区别是，子数组不能搞[1,2,4]这样跳过3的，而子集合可以。前者可以每次新加一个元素。加了的可以继续加，没加的就不能加了，后者无此限制。子集里面，每次都是给整个结果里每个元素加新元素，而子数组里，每次只给上一次的计算结果里加新元素。由于子数组必须是连续的，所以个数比子集合要少一些，生成的方法也是在现有的集合都加入当前数字，并每次新加一个只有当前数字的集合，顺序如下：

[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，先放到现有集合中，变成 [001 011]，然后再新建一个自己的集合 [011]，对于后面的数字都是同样的操作，最后就有5个不同的集合，代表了所有的子数组，对每个集合都计算总'或'值，可以得到：

001
011 011
111 111 100
111 111 110 110
111 111 111 111 101

之前提到了，若对于每个集合都一个一个的'或'起来，将会十分的不高效，而其实这里面可能会有许多重复值，所以对重复值只需要保留一个，实际上就可以变成：

001
011
111 100
111 110
111 101

这样数字就减少了很多，使得计算效率也就大大的提高了。具体的做法是，开始先建立两个 HashSet，分别是 res 和 cur，然后遍历数组A，对于每个遍历到的数字，首先生成一个自己的集合 tmp，然后遍历集合 cur 中的所有数字，将当前数字和 cur 中的每个数字相'或'，并存入 tmp 中，由于 HashSet 可以自动去重复，所以 tmp 中保存的只有不同的值，然后将 tmp 全部赋值给 cur，再将 cur 中的所有值加入结果 res 中，由于结果 res 也是 HashSet，也可以自动去重复，最后留在 res 中的就是所有不同的子数组的总'或'值，参见代码如下：

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& A) {
        unordered_set<int> res, cur;
        for (int i : A) {
            unordered_set<int> tmp = {i};
            for (int j : cur) tmp.insert(i | j);
            cur = tmp;
            for (int j : cur) res.insert(j);
        }
        return res.size();
    }
};

Github 同步地址:

#898

参考资料：

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

https://leetcode.com/problems/bitwise-ors-of-subarrays/discuss/165859/C%2B%2B-O(kN)-solution

https://leetcode.com/problems/bitwise-ors-of-subarrays/discuss/165881/C%2B%2BJavaPython-O(30N)

LeetCode All in One 题目讲解汇总(持续更新中...)