982. Triples with Bitwise AND Equal To Zero

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation