class Solution {
public:
int subarrayBitwiseORs(vector<int>& arr) {
}
};
898. 子数组按位或操作
我们有一个非负整数数组 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 * 1040 <= nums[i] <= 109原站题解
golang 解法, 执行用时: 172 ms, 内存消耗: 33.7 MB, 提交时间: 2023-09-18 17:49:28
// 模板可以
// 求出所有子数组的按位或的结果，以及值等于该结果的子数组的个数。
// 求按位或结果等于任意给定数字的子数组的最短长度/最长长度
func subarrayBitwiseORs2(arr []int) int {
n := len(arr)
type pair struct{ or, i int }
ors := []pair{} // 按位或的值 + 对应子数组的右端点的最小值
cnt := map[int]struct{}{}
for i := n - 1; i >= 0; i-- {
num := arr[i]
ors = append(ors, pair{0, i})
// for j := range ors {
// ors[j].or |= arr[i]
// cnt[ors[j].or] = struct{}{}
// }
ors[0].or |= num
cnt[ors[0].or] = struct{}{}
k := 0
for _, p := range ors[1:] {
p.or |= num
cnt[p.or] = struct{}{}
if ors[k].or == p.or {
ors[k].i = p.i // 合并相同值，下标取最小的
} else {
k++
ors[k] = p
}
}
ors = ors[:k+1]
}
return len(cnt)
}
// 暴力剪枝
func subarrayBitwiseORs(arr []int) int {
res := make(map[int]int)
for i:=0; i<len(arr); i++ {
res[arr[i]] = 1
for j:=i-1; j>-1; j-- {
if ( arr[j]|arr[i] == arr[j] ) {
break
}
arr[j] |= arr[i]
res[arr[j]] = 1
}
}
return len(res)
}
python3 解法, 执行用时: 548 ms, 内存消耗: 42.5 MB, 提交时间: 2023-09-18 17:47:19
class Solution:
def subarrayBitwiseORs(self, arr: List[int]) -> int:
ans = set()
cur = {0}
for x in arr:
cur = {x | y for y in cur} | {x}
ans |= cur
return len(ans)
java 解法, 执行用时: 353 ms, 内存消耗: 64.3 MB, 提交时间: 2023-09-18 17:46:55
class Solution {
public int subarrayBitwiseORs(int[] A) {
Set<Integer> ans = new HashSet();
Set<Integer> cur = new HashSet();
cur.add(0);
for (int x: A) {
Set<Integer> cur2 = new HashSet();
for (int y: cur)
cur2.add(x | y);
cur2.add(x);
cur = cur2;
ans.addAll(cur);
}
return ans.size();
}
}
cpp 解法, 执行用时: 400 ms, 内存消耗: 95.9 MB, 提交时间: 2023-09-18 17:44:42
class Solution {
public:
int subarrayBitwiseORs(vector<int>& nums) {
int n = nums.size();
vector<int> ors;
unordered_set<int> st;
for (int i = n - 1; i >= 0; --i) {
ors.emplace_back(0);
ors[0] |= nums[i];
int k = 0;
for (int j = 1; j < ors.size(); ++j) {
ors[j] |= nums[i];
if (ors[k] == ors[j])
continue;
else ors[++k] = ors[j];
}
ors.resize(k + 1);
for(auto num:ors)
st.insert(num);
}
return st.size();
}
};