leetcode
leetcode 801 ~ 850
子数组按位或操作

子数组按位或操作

难度:

标签:

题目描述

代码结果

运行时间: 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存储了到当前元素为止,所有以当前元素结尾的子数组的按位或结果。当处理新的元素x时,我们不需要重新计算从头开始的所有子数组,而是利用已经计算过的结果s1。新建一个集合s2,首先加入元素x,然后对于s1中的每个元素y,计算y|x并添加到s2中。这样,s2就包含了所有以新元素x结尾的子数组按位或结果,而无需重复计算之前元素的按位或结果。通过这种方式,算法避免了对已计算结果的重复计算,减少了计算量。
🦆
在题解中,为什么每次迭代都要更新s1为s2而不是将s2的结果直接加入到s1中?这样做有什么特别的意义或优势吗?
这么做的主要目的是保证s1总是包含以当前遍历到的元素x结尾的所有子数组的按位或结果。如果将s2的结果直接加入到s1中,s1就会包含不同元素结尾的子数组结果,这会导致在后续计算中产生重复和错误的结果。通过设置s1为s2,我们确保每次迭代都是基于最新的元素x,从而能正确生成所有以该元素结尾的子数组按位或结果。这样的处理保证了结果的正确性和算法的高效性。
🦆
题解提到按位或操作的结果通常趋向于包含更多的1比特,这一性质是如何影响算法效率的?
按位或操作的特性是,一旦某个比特位在操作中变成了1,它在后续的按位或操作中将永远是1。这意味着随着操作的进行,生成的数字将趋向于稳定,即不会再有新的1比特位出现。因此,在处理较长的数组时,尽管子数组的数量是指数级增长的,但实际上由于按位或操作的这一性质,有效的不同结果的数量是有限的,通常远小于子数组的总数。这大大减少了需要处理的数据量,提高了算法的效率。

相关问题