[LeetCode] 982. Triples with Bitwise AND Equal To Zero

[grandyang]

Given an array of integers A, find the number of triples of indices (i, j, k) such that:

• 0 <= i < A.length
• 0 <= j < A.length
• 0 <= k < A.length
• A[i] & A[j] & A[k] == 0, where & represents the bitwise-AND operator.

Example 1:

Input: [2,1,3]
Output: 12
Explanation: We could choose the following i, j, k triples:
(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

Note:

1. 1 <= A.length <= 1000
2. 0 <= A[i] < 2^16

这道题给了一个数组，定义了一种三元组，使得这三个数字相‘与’得到为0，问有多少种不同的组合。根据题目中的例子可以发现，数字是可以重复使用的，当然最无脑暴力的方法就是遍历所有的三个数字的组合，直接相‘与’看是否为0，但是这种做法完全不尊重 OJ，也不尊重这道题的 Hard 标签。这道题给的提示使用动态规划 Dynamic Programming 来做，但是博主按照论坛上的一种高分的 DP 方法写的 C++ 版本的还是超时了，看来这道题的 OJ 真的是很挑剔呢。其实对于三元组的问题，有一种很好的思路就是先确定下其中的两个数字，再去找第三个数字，比较典型的就是 3Sum。而这道题由于是要求三个数字相‘与’，若先将其中的两个数字相‘与’，然后再去找第三个数字，实际上就相当于降维了，难度也就降低了。这里使用一个 HashMap 来建立相‘与’值与其出现次数之间的映射，遍历任意两个数字，然后相‘与’，并将其在 HashMap 中的值自增1。然后再次遍历所有数字，对于每个数字都遍历一遍 HashMap，若数字和某个 key 值相‘与’为0，则将对应的 value 值加入结果 res 中，是不是感觉有一种 Two Sum 的即视感，还是那句话 ‘平生不识 TwoSum，刷尽 LeetCode 也枉然’，参见代码如下：

解法一：

class Solution {
public:
    int countTriplets(vector<int>& A) {
        int res = 0;
        unordered_map<int, int> m;
        for (int a : A) {
            for (int b : A) {
                ++m[a & b];
            }
        }
        for (int num : A) {
            for (auto a : m) {
                if ((num & a.first) == 0) {
                    res += a.second;
                }
            }
        }
        return res;
    }
};

这里由于知道了数字的范围，所以可以直接使用一个数组 cnt，大小为 1 << 16，初始化为 -1，不过这里的数组值表示的含义和上面略有不同，其中 cnt[i] 表示的是可以跟 i 相‘与’为0的数字的个数。然后还是遍历任意两个数字，求出相‘与’值，若这个值在数组中的值为 -1，表示还没出现过，则将其在数组中的值改为0，然后遍历一遍数组，只要有和之前的相‘与’值再次相‘与’，若得到0的话，则对应的映射值自增1。最后还要把映射值加到结果 res 中即可，参见代码如下：

解法二：

class Solution {
public:
    int countTriplets(vector<int>& A) {
        int res = 0;
        vector<int> cnt(1 << 16, -1);
        for (int a : A) {
            for (int b : A) {
                int x = a & b;
                if (cnt[x] == -1) {
                    cnt[x] = 0;
                    for (int num : A) {
                        if ((x & num) == 0) ++cnt[x];
                    }
                }
                res += cnt[x];
            }
        }
        return res;
    }
};

Github 同步地址:

#982

类似题目：

参考资料：

https://leetcode.com/problems/triples-with-bitwise-and-equal-to-zero/

https://leetcode.com/problems/triples-with-bitwise-and-equal-to-zero/discuss/227309/C%2B%2B-naive-O(n-*-n)

https://leetcode.com/problems/triples-with-bitwise-and-equal-to-zero/discuss/226721/Java-DP-O(3-*-216-*-n)-time-O(216)-space

https://leetcode.com/problems/triples-with-bitwise-and-equal-to-zero/discuss/226778/C%2B%2B-20-lines56msenumerate-with-memory-(with-Chinese-translation)

LeetCode All in One 题目讲解汇总(持续更新中...)