0898. Bitwise ORs of Subarrays¶
题目信息¶
- 题号:
0898
- 难度:
Medium
- 主题:
数组、连续子数组、按位或
- 原题:
- 重点:
对每个非空连续子数组计算全部元素的按位或,返回不同结果值的数量;相同结果只计一次
题目重述¶
给定非负整数数组 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,去重后只有一种结果。