![](https://img.shields.io/badge/难度-简单-4051B5?style=flat-square)
题目描述
给定三个整数数组 a
,b
和 c
,返回组内元素按位 XOR
有 偶数 个 设置位 的三元组 (a[i], b[j], c[k])
的数量。
示例 1:
输入:a = [1], b = [2], c = [3]
输出:1
解释:
只有一个三元组 (a[0], b[0], c[0])
并且它们的 XOR
为:1 XOR 2 XOR 3 = 002
。
示例 2:
输入:a = [1,1], b = [2,3], c = [1,5]
输出:4
解释:
考虑以下 4 个三元组:
(a[0], b[1], c[0])
: 1 XOR 3 XOR 1 = 0112
(a[1], b[1], c[0])
: 1 XOR 3 XOR 1 = 0112
(a[0], b[0], c[1])
: 1 XOR 2 XOR 5 = 1102
(a[1], b[0], c[1])
: 1 XOR 2 XOR 5 = 1102
提示:
1 <= a.length, b.length, c.length <= 100
0 <= a[i], b[i], c[i] <= 100
解法
方法一:位运算
对于两个整数,异或结果中 $1$ 的个数的奇偶性,取决于两个整数的二进制表示中 $1$ 的个数的奇偶性。
我们可以用三个数组 cnt1
、cnt2
、cnt3
分别记录数组 a
、b
、c
中每个数的二进制表示中 $1$ 的个数的奇偶性。
然后我们在 $[0, 1]$ 的范围内枚举三个数组中的每个数的二进制表示中 $1$ 的个数的奇偶性,如果三个数的二进制表示中 $1$ 的个数的奇偶性之和为偶数,那么这三个数的异或结果中 $1$ 的个数也为偶数,此时我们将这三个数的组合数相乘累加到答案中。
最后返回答案即可。
时间复杂度 $O(n)$,其中 $n$ 为数组 a
、b
、c
的长度。空间复杂度 $O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def tripletCount(self, a: List[int], b: List[int], c: List[int]) -> int:
cnt1 = Counter(x.bit_count() & 1 for x in a)
cnt2 = Counter(x.bit_count() & 1 for x in b)
cnt3 = Counter(x.bit_count() & 1 for x in c)
ans = 0
for i in range(2):
for j in range(2):
for k in range(2):
if (i + j + k) & 1 ^ 1:
ans += cnt1[i] * cnt2[j] * cnt3[k]
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | class Solution {
public int tripletCount(int[] a, int[] b, int[] c) {
int[] cnt1 = new int[2];
int[] cnt2 = new int[2];
int[] cnt3 = new int[2];
for (int x : a) {
++cnt1[Integer.bitCount(x) & 1];
}
for (int x : b) {
++cnt2[Integer.bitCount(x) & 1];
}
for (int x : c) {
++cnt3[Integer.bitCount(x) & 1];
}
int ans = 0;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 2; ++k) {
if ((i + j + k) % 2 == 0) {
ans += cnt1[i] * cnt2[j] * cnt3[k];
}
}
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | class Solution {
public:
int tripletCount(vector<int>& a, vector<int>& b, vector<int>& c) {
int cnt1[2]{};
int cnt2[2]{};
int cnt3[2]{};
for (int x : a) {
++cnt1[__builtin_popcount(x) & 1];
}
for (int x : b) {
++cnt2[__builtin_popcount(x) & 1];
}
for (int x : c) {
++cnt3[__builtin_popcount(x) & 1];
}
int ans = 0;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 2; ++k) {
if ((i + j + k) % 2 == 0) {
ans += cnt1[i] * cnt2[j] * cnt3[k];
}
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | func tripletCount(a []int, b []int, c []int) (ans int) {
cnt1 := [2]int{}
cnt2 := [2]int{}
cnt3 := [2]int{}
for _, x := range a {
cnt1[bits.OnesCount(uint(x))%2]++
}
for _, x := range b {
cnt2[bits.OnesCount(uint(x))%2]++
}
for _, x := range c {
cnt3[bits.OnesCount(uint(x))%2]++
}
for i := 0; i < 2; i++ {
for j := 0; j < 2; j++ {
for k := 0; k < 2; k++ {
if (i+j+k)%2 == 0 {
ans += cnt1[i] * cnt2[j] * cnt3[k]
}
}
}
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 | function tripletCount(a: number[], b: number[], c: number[]): number {
const cnt1: [number, number] = [0, 0];
const cnt2: [number, number] = [0, 0];
const cnt3: [number, number] = [0, 0];
for (const x of a) {
++cnt1[bitCount(x) & 1];
}
for (const x of b) {
++cnt2[bitCount(x) & 1];
}
for (const x of c) {
++cnt3[bitCount(x) & 1];
}
let ans = 0;
for (let i = 0; i < 2; ++i) {
for (let j = 0; j < 2; ++j) {
for (let k = 0; k < 2; ++k) {
if ((i + j + k) % 2 === 0) {
ans += cnt1[i] * cnt2[j] * cnt3[k];
}
}
}
}
return ans;
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
|