2021

2023-03-23 12:01| 来源: 网络整理| 查看: 265

1310 子数组异或查询问题描述：

有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor … xor arr[Ri]）作为本次查询的结果。并返回一个包含给定查询 queries 所有结果的数组。

示例1：输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]] 输出：[2,7,14,8] 解释：数组中元素的二进制表示形式是： 1 = 0001 3 = 0011 4 = 0100 8 = 1000 查询的 XOR 值为： [0,1] = 1 xor 3 = 2 [1,2] = 3 xor 4 = 7 [0,3] = 1 xor 3 xor 4 xor 8 = 14 [3,3] = 8 示例2：输入：arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]] 输出：[8,0,4,4] 思路：

这个问题乍一看不难，毕竟常理来说遍历一趟就什么都解决了，但这里如果遍历的话，我们需要重复计算的内容太多了，所以这里需要对之前计算的东西做一个保存，才能在时间上保证可以通过。

第一个思路是新建一个二维数组，保存从 i 到 j 的异或值，后面输出的时候直接使用即可，但是这里存在一个问题，就是我们需要new的这个数组实在是太大了，并且里面有将近一半的空间是没有用的，因为我们只需要 j 大于等于 i 的那一部分值，反映到矩阵中就是一个矩阵的上半部分。所以对空间产生了极大地浪费。

初级实现的时候，时间没有爆炸，空间爆炸了。

Java代码： /** * @Description: 力扣1310题题解 * @return: 返回结果 * @Author: Mr.Gao * @Date: 2021/5/12 */ public int[] xorQueries(int[] arr, int[][] queries) { int n = arr.length; int[][] temp = new int[n][n]; for (int i = 0; i if(i==j){ temp[i][j] = arr[i]; }else{ temp[i][j] = temp[i][j-1]^arr[j]; } } } int m = queries.length; int[] re = new int[m]; for (int i = 0; i int n = arr.length; //temp【0】保存从0到j的所有异或值，temp【1】保存从j到n-1的所有异或值。 int[][] temp = new int[2][n]; //x保存arr中所有元素的异或值 int x = arr[0]; temp[0][0] = arr[0]; for(int i=1;i temp[1][i] = temp[1][i+1]^arr[i]; } int m = queries.length; int[] re = new int[m]; for (int i = 0; i

【本文地址】

公司简介

联系我们