Keshawn_lu's Blog

Leetcode 5405. 形成两个异或相等数组的三元组数目

字数统计: 450阅读时长: 2 min
2020/05/10 Share

题目简介:

给你一个整数数组 arr

现需要从数组中取三个下标 ijk ,其中 (0 <= i < j <= k < arr.length)

ab 定义如下:

  • a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
  • b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

注意:^ 表示 按位异或 操作。

请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。

示例 1:

1
2
3
输入:arr = [2,3,1,6,7]
输出:4
解释:满足题意的三元组分别是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4)

示例 2:

1
2
输入:arr = [1,1,1,1,1]
输出:10

示例 3:

1
2
输入:arr = [2,3]
输出:0

示例 4:

1
2
输入:arr = [1,3,5,7,9]
输出:3

示例 5:

1
2
输入:arr = [7,11,12,9,5,2,7,17,22]
输出:8

提示:

  • 1 <= arr.length <= 300
  • 1 <= arr[i] <= 10^8

思路:周赛时候的一道题,本来以为三层循环过不了的…没想到竟然过了。首先是设置一个数组res[j][i] (i <= j)代表arr[i]arr[j]的异或总结果,将这个数组准备好以后,j0开始,将res[j - 1][i]res[k][j]的值进行比较,即ab的比较。

  • a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
  • b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

相等则数量+1。

代码如下:

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
35
36
37
38
class Solution {
public:
int countTriplets(vector<int>& arr) {

int count = 0;

int res[301][301] = {0};

for(int i = 0; i < arr.size(); i++){

int temp = arr[i];
res[i][i] = temp; //一个数的异或结果,即本身
for(int j = i - 1; j >= 0; j--){

temp = temp ^ arr[j];
res[i][j] = temp;
}

}


for(int j = 1; j < arr.size(); j++){

for(int i = 0; i < j; i++){

for(int k = arr.size() - 1; k >= j; k--){

if(res[j - 1][i] == res[k][j])
count++;
}

}
}

return count;

}
};
CATALOG
  1. 1. 题目简介: