README.md

898. 子数组按位或操作

English Version

题目描述

我们有一个非负整数数组 arr 。

对于每个（连续的）子数组 sub = [arr[i], arr[i + 1], ..., arr[j]] （ i <= j），我们对 sub 中的每个元素进行按位或操作，获得结果 arr[i] | arr[i + 1] | ... | arr[j] 。

返回可能结果的数量。 多次出现的结果在最终答案中仅计算一次。

 

示例 1：

输入：arr = [0]
输出：1
解释：
只有一个可能的结果 0 。

示例 2：

输入：arr = [1,1,2]
输出：3
解释：
可能的子数组为 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。
产生的结果为 1，1，2，1，3，3 。
有三个唯一值，所以答案是 3 。

示例 3：

输入：arr = [1,2,4]
输出：6
解释：
可能的结果是 1，2，3，4，6，以及 7 。

 

提示：

• 1 <= nums.length <= 5 * 104
• 0 <= nums[i] <= 109​​​​​​​

解法

Python3

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        s = set()
        prev = 0
        for i, v in enumerate(arr):
            prev |= v
            curr = 0
            for j in range(i, -1, -1):
                curr |= arr[j]
                s.add(curr)
                if curr == prev:
                    break
        return len(s)

Java

class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> s = new HashSet<>();
        int prev = 0;
        for (int i = 0; i < arr.length; ++i) {
            prev |= arr[i];
            int curr = 0;
            for (int j = i; j >= 0; --j) {
                curr |= arr[j];
                s.add(curr);
                if (curr == prev) {
                    break;
                }
            }
        }
        return s.size();
    }
}

C++

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& arr) {
        unordered_set<int> s;
        int prev = 0;
        for (int i = 0; i < arr.size(); ++i) {
            prev |= arr[i];
            int curr = 0;
            for (int j = i; ~j; --j) {
                curr |= arr[j];
                s.insert(curr);
                if (curr == prev) break;
            }
        }
        return s.size();
    }
};

Go

func subarrayBitwiseORs(arr []int) int {
	s := map[int]bool{}
	prev := 0
	for i, v := range arr {
		prev |= v
		curr := 0
		for j := i; j >= 0; j-- {
			curr |= arr[j]
			s[curr] = true
			if curr == prev {
				break
			}
		}
	}
	return len(s)
}

...