子数组按位或操作
难度:
标签:
题目描述
代码结果
运行时间: 398 ms, 内存: 42.0 MB
/*
* 思路:
* 使用Java Stream实现相同的逻辑。
* 由于Stream的特性,我们需要转换为并行流并且对结果进行收集。
*/
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class Solution {
public int subarrayBitwiseORs(int[] arr) {
Set<Integer> res = new HashSet<>();
Set<Integer> cur = new HashSet<>();
for (int num : arr) {
cur = Stream.concat(cur.stream(), Stream.of(0))
.map(x -> x | num)
.collect(Collectors.toSet());
res.addAll(cur);
}
return res.size();
}
}
解释
方法:
这个题解采用了一个动态的方式来避免重复计算子数组按位或的结果。首先,使用一个集合ans来存储所有唯一的按位或结果。然后,对于每个元素x,用一个新集合s2来存储以x结尾的所有子数组的按位或结果。这里s2初始化包含元素x自身。对于上一步的结果集合s1,对其中每个元素y执行 y | x 操作,并将结果添加到s2中。这样可以确保考虑了所有以x结尾的子数组的按位或结果。最后,将s2中的所有结果合并到ans中,并更新s1为s2以供下一次循环使用。这个方法有效地利用了已有的按位或结果来生成新的结果,避免了冗余计算。
时间复杂度:
O(n^2)
空间复杂度:
O(n)
代码细节讲解
🦆
解题思路中提到的动态方式是如何避免重复计算子数组按位或结果的?能详细解释这个过程吗?
▷🦆
在题解中,为什么每次迭代都要更新s1为s2而不是将s2的结果直接加入到s1中?这样做有什么特别的意义或优势吗?
▷🦆
题解提到按位或操作的结果通常趋向于包含更多的1比特,这一性质是如何影响算法效率的?
▷