0898. Bitwise ORs of Subarrays

题目信息

题号:

0898

难度:

Medium

主题:

数组、连续子数组、按位或

原题:

LeetCode 0898

重点:

对每个非空连续子数组计算全部元素的按位或,返回不同结果值的数量;相同结果只计一次

题目重述

给定非负整数数组 arr。对于每个非空连续子数组,把其中全部元素进行按位或运算,得到该子数组的结果值。

请返回所有非空连续子数组能够产生的不同按位或结果数量。不同下标区间即使产生相同结果,也只为该结果贡献一次;不能选择不连续的元素。

1 <= arr.length <= 5 * 10^4,0 <= arr[i] <= 10^9。

自建示例

各长度区间产生六种不同结果:

输入:arr = [5,2,8]
输出:6
解释:三个单元素子数组得到 5、2、8;相邻二元素子数组得到 5 | 2 = 7 和 2 | 8 = 10;整个数组得到 5 | 2 | 8 = 15,因此不同结果为 {2,5,7,8,10,15}。

多个全零区间只有一种结果:

输入:arr = [0,0]
输出:1
解释:两个单元素子数组和整个二元素子数组的按位或结果都为 0,去重后只有一种结果。