leetcode
leetcode 901 ~ 950
按位与为零的三元组

按位与为零的三元组

难度:

标签:

题目描述

代码结果

运行时间: 191 ms, 内存: 16.6 MB


/*
 * 题目思路:
 * 1. 使用Java Streams来遍历所有可能的三元组 (i, j, k),并统计满足条件的数目。
 * 2. 使用三重流分别遍历 i, j, k,并过滤 nums[i] & nums[j] & nums[k] == 0 的三元组。
 */
import java.util.stream.IntStream;

public class Solution {
    public int countTriplets(int[] nums) {
        int n = nums.length;
        return (int) IntStream.range(0, n).boxed()
                .flatMap(i -> IntStream.range(0, n).boxed()
                        .flatMap(j -> IntStream.range(0, n).boxed()
                                .filter(k -> (nums[i] & nums[j] & nums[k]) == 0)
                        )
                ).count();
    }
}

解释

方法:

该题解采用了一种利用位运算的技巧来解决问题。首先找到数组中最大的数,并确定一个足够大的二进制数u,使得u是第一个大于数组中任何数的2的幂。这是为了方便后续的位运算。然后,使用一个数组cnt来记录每个可能的位模式(直到u-1)在数组中出现的次数。对于每个数m,在数组nums中,先计算其补码(m^=u-1),然后枚举其所有可能的非空子集,并更新cnt数组。最后,通过双重循环遍历nums数组,使用cnt数组计算所有满足条件的(i, j, k)三元组数量。具体来说,对于每对数x和y,寻找在cnt数组中x与y按位与的结果作为索引的值,这个值即表示有多少个k使得nums[k]与x和y按位与的结果为0。

时间复杂度:

O(n*u + n^2)

空间复杂度:

O(u + n)

代码细节讲解

🦆
为什么在确定变量u时选择它为大于数组中任何数的最小的2的幂,这个选择对算法的效率或结果有什么关键影响?
选择变量u为大于数组中任何数的最小的2的幂主要是为了简化计算和优化性能。首先,这样做可以确保所有数都可以在u的位宽内表示,这对后续的位运算(如补码计算和子集枚举)是必要的。其次,使用2的幂作为边界可以使得位运算(如左移、按位与)更为高效,因为这些操作在计算机内部是优化过的。此外,这种选择使得数组cnt的大小刚好足够覆盖所有可能的位模式,从而避免了不必要的内存使用和计算复杂度。
🦆
在计算每个数的补码时,使用了`m ^= u - 1`这个操作。这个补码在算法中扮演了什么角色,为什么需要这样计算补码?
在算法中,计算每个数的补码(使用`m ^= u - 1`)是为了将原始数据转换为一种形式,使得后续可以通过枚举子集来找到所有可能的位模式,这些位模式在与其他数进行按位与操作后可能产生零结果。这个转换实际上是将原始数值进行按位取反操作,但限定在u的位宽内。这样做的目的是为了便于使用子集枚举算法,直接得到补码对应的所有子集,从而简化查找过程。
🦆
算法中提到枚举每个数的所有非空子集,这一步是如何通过位操作实现的?具体的位操作`s = (s - 1) & m`如何保证枚举到所有子集?
在算法中,利用位操作` s = (s - 1) & m`来枚举一个数m的所有非空子集,是一种高效的子集枚举技术。这个操作的原理是:`s - 1`操作会将数s的二进制表示中最低位的1变为0,并将此1右边的所有0变为1。接下来的`& m`操作保证了只考虑那些原始数m中为1的位。这种方法通过逐步减少s的最低位的1,并应用与m的按位与,能够依次访问从m的最大子集到最小子集的所有非空子集,直到s为0停止。这确保了所有有效的子集被枚举出来,而不遗漏任何一个。

相关问题