0982：按位与为零的三元组（2084 分）

2019-01-27 约 531 字预计阅读 2 分钟次阅读

力扣第 121 场周赛第 4 题

题目

给你一个整数数组 nums ，返回其中 按位与三元组 的数目。

按位与三元组 是由下标 (i, j, k) 组成的三元组，并满足下述全部条件：

0 <= i < nums.length
0 <= j < nums.length
0 <= k < nums.length
nums[i] & nums[j] & nums[k] == 0 ，其中 & 表示按位与运算符。

示例 1：

输入：nums = [2,1,3]
输出：12
解释：可以选出如下 i, j, k 三元组：
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2

示例 2：

输入：nums = [0,0,0]
输出：27

提示：

1 <= nums.length <= 1000
0 <= nums[i] < 2¹⁶

分析

#1

考虑将二元组的结果存在计数器中，然后再遍历第三个数即可。

1
2
3
4


class Solution:
    def countTriplets(self, nums: List[int]) -> int:
        ct = Counter(x&y for x in nums for y in nums)
        return sum(ct[y] for x in nums for y in ct if x&y==0)

2463 ms

#2

位运算卷积问题，可以用快速沃尔什变换优化。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


def fwt(A,L,tp):
    for x in range(L):
        k = 1<<x
        for i in range(0,1<<L,k<<1):
            for j in range(k):
                A[i+j] += A[i+j+k]*tp

class Solution:
    def countTriplets(self, nums: List[int]) -> int:
        L = max(nums).bit_length()
        A = [0]*(1<<L)
        for x in nums:
            A[x] += 1
        fwt(A,L,1)
        C = [a*a*a for a in A]
        fwt(C,L,-1)
        return C[0]

652 ms

#3

由于最后只求 C[0]，可以直接根据 fwt 的过程计算。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


def fwt(A,L,tp):
    for x in range(L):
        k = 1<<x
        for i in range(0,1<<L,k<<1):
            for j in range(k):
                A[i+j] += A[i+j+k]*tp

class Solution:
    def countTriplets(self, nums: List[int]) -> int:
        L = max(nums).bit_length()
        A = [0]*(1<<L)
        for x in nums:
            A[x] += 1
        fwt(A,L,1)
        return sum(a*a*a*(-1 if i.bit_count()%2 else 1) for i,a in enumerate(A))

359 ms

目录

0982：按位与为零的三元组（2084 分）

题目

分析

#1

#2

#3

解答