33、按位与为零的三元祖

题目描述：
给定一个整数数组 A，找出索引为 (i, j, k) 的三元组，使得：

0 <= i < A.length
0 <= j < A.length
0 <= k < A.length
A[i] & A[j] & A[k] == 0，其中 & 表示按位与（AND）操作符。

示例：

输入：[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

提示：

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

使用map来存储前两个数字与出现的数字次数，然后我们进行第三个数字的与，如果为零，则加上value，最后返回。

class Solution {public int numDistinct(String S, String T) {int dp[][] = new int[T.length() + 1][S.length() + 1];for (int i = 0; i < dp[0].length; i++) {dp[0][i] = 1;}for (int i = 1; i < dp.length; i++) {for (int j = 1; j < dp[0].length; j++) {dp[i][j] = dp[i][j - 1];if(T.charAt(i - 1) == S.charAt(j - 1)){dp[i][j] += dp[i-1][j-1];}}}return dp[T.length()][S.length()];}
}

使用dp数组，目前没有看懂

class Solution {public int countTriplets(int[] A) {int len = 1 << 16;int[] dp = new int[len];int res = 0;Arrays.fill(dp, -1);for (int i : A) {for (int j : A) {int num = i & j;if (dp[num] == -1) {dp[num]++;for (int k : A) {if ((k & num) == 0) {dp[num]++;}}}res += dp[num];}}return res;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！