标签：bsp 三元组 function rip -o col @param UNC ==
题目来源：1442. 形成两个异或相等数组的三元组数目
给你一个整数数组 arr 。
现需要从数组中取三个下标 i、j 和 k ，其中 (0
a 和 b 定义如下：
a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]
注意：^ 表示 按位异或 操作。
请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。
解题思路： 动态规划
1、我们观察到所求的数组区间是[i,j-1][j,k],满足a==b,根据异或的特性 a^b=0，可以将问题转化为求合并后区间[i,k] arr[i]^...^arr[k] = 0
2、arr[i]^...^arr[k] = 0 可以转化为 arr[0]^...^a[i-1] ^ arr[0]^...^arr[i-1]^arr[i]^...^arr[k] = 0
即 arr[0]^...^a[i-1] ^arr[0]^...^a[k] =0
3、假设dp[i] 为 arr[0]^...^arr[i], 则有 dp[i-1]^dp[k] = 0
4、得到[i,k]区间后，再求j
/**
* @param {number[]} arr
* @return {number}
*/
var countTriplets = function(arr) {
let n = arr.length;
let dp = new Array(n).fill(0);
let res = [];
let count=0;
for(let i = 0;i){
dp[i] = (i==0?0:dp[i-1]) ^ arr[i];
if(dp[i] == 0){
res.push({‘i‘:0,‘k‘:i});
}
}
for(let i=0;i){
for(let j=i+1;j){
if((dp[i]^dp[j]) === 0){
res.push({‘i‘:i+1,‘k‘:j});
}
}
}
while(res.length>0){
let cur = res.pop();
for(let j=cur.i+1;j){
let left = (cur.i === j-1)?(dp[cur.i]^dp[cur.i-1]):(dp[cur.i-1]^dp[j-1]);
let right = (cur.k===j)?(dp[cur.k]^dp[cur.k-1]):(dp[cur.k]^dp[j-1]);
if( left === right){
count++;
}
}
}
return count;
};
let arr = [2,3,1,6,7]
console.log(arr, countTriplets(arr))
arr = [1,1,1,1,1]
console.log(arr, countTriplets(arr))
arr =[2,3]
console.log(arr, countTriplets(arr))
arr = [1,3,5,7,9]
console.log(arr, countTriplets(arr))
arr = [7,11,12,9,5,2,7,17,22]
console.log(arr, countTriplets(arr))
示例 1：
输入：arr = [2,3,1,6,7]
输出：4
解释：满足题意的三元组分别是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4)
示例 2：
输入：arr = [1,1,1,1,1]
输出：10
示例 3：
输入：arr = [2,3]
输出：0
示例 4：
输入：arr = [1,3,5,7,9]
输出：3
示例 5：
输入：arr = [7,11,12,9,5,2,7,17,22]
输出：8
提示：
1
1
1442. 形成两个异或相等数组的三元组数目
标签：bsp 三元组 function rip -o col @param UNC ==
原文地址：https://www.cnblogs.com/yanjianjiang/p/14780140.html