X

LEETCODE 1442. Count Triplets That Can Form Two Arrays of Equal XOR 解题思路分析

题目大意:

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

给你一个整数数组 arr 。

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

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:

输入: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 <= arr.length <= 300
  • 1 <= arr[i] <= 10^8

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1442

解题思路分析:

这道题目实际上可以这样理解,给定一个数组,然后让你找到2个子数组,两个子数组的范围可以表示为:

[i, j-1] // 数组1的范围
[j, k] // 数组2的范围
// 0 <= i < j <= k < arr.length

最后求出这两个子数组中所有元素亦或值相同的可能。

由于题目给出的数据规模并不大,因此暴力解法是可行的。我们使用三层循环来分别遍历i,j,k这三个变量。其中i的取值范围是下标0到数组最后一位。j的取值范围是i加一到数组最后一位,k的取值范围为j到数组最后一位。循环中我们分别查看两个子数组的亦或值是否相同即可。另外,本题为了提高效率,我们不用每次循环都去求一遍两个数组的亦或值。这里我们可以采用前缀数组来简化计算步骤。之前的文章我们多次讲过前缀和数组,而前缀亦或数组与前缀和数组原理形同,我们也曾提到过。(参考LEETCODE 1310. XOR Queries of a Subarray 解题思路分析

比如我们定义前缀数组为pre[],其中pre[0]等于arr[0],pre[i]=pre[i-1]^arr[i]。因此对于任意一个区间的[x,y]的亦或值我们可以通过前缀数组来取得,即:

int xorXY = pre[x-1] ^ pre[y]; // 当x大于0时,区间x到y之间数值的亦或值
int xorXY = pre[y] // 当x等于0时

实现代码:

public int countTriplets(int[] arr) {
    // 前缀亦或数组
    int[] pre = new int[arr.length];
    pre[0]=arr[0];
    for(int i=1;i<arr.length;i++){
        pre[i] = (arr[i]^pre[i-1]);
    }
    int res=0; // 返回结果
    // 循环每一种情况
    for(int i=0;i<arr.length;i++){
        for(int j=i+1;j<arr.length;j++){
            for(int k=j;k<arr.length;k++){
                int x1; // 第一个数组的亦或值
                if(i==0){
                    x1=pre[j-1];
                }else{
                    x1=(pre[i-1]^pre[j-1]);
                }
                // 第一个数组与第二个数组亦或值相同时,结果加一
                if(x1==(pre[j-1]^pre[k])){
                    res++;
                }
            }
        }
    }
    return res;
}

本题解法执行时间为48ms。

Runtime: 48 ms, faster than 25.00% of Java online submissions for Count Triplets That Can Form Two Arrays of Equal XOR.

Memory Usage: 36.9 MB, less than 100.00% of Java online submissions for Count Triplets That Can Form Two Arrays of Equal XOR.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1442-count-triplets-that-can-form-two-arrays-of-equal-xor-解题思路分析/
Categories: leetcode
kwantong:

View Comments (0)