leetcode每日一题：子数组异或查询

引言

        今天的每日一题原题是3375. 使数组的值全部为 K 的最少操作次数，比较水，可以分成2种情况：

• 存在比k更小的数，由于每次操作只能使得部门数变小，但是不能把任何数变大，所以肯定无法告竣
  
• 不存在比k更小的数，那操作的次数就是比k大的不同数值的数目
  

更换成前几天碰到的更有意思的一题来写这个每日一题。
标题

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

示例 1：

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

复制代码

示例 2：

1. 输入：arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
2. 输出：[8,0,4,4]

复制代码

提示：

• 1 <= arr.length <= 3 * 10^4
  
• 1 <= arr <= 10^9
  
• 1 <= queries.length <= 3 * 10^4
  
• queries.length == 2
  
• 0 <= queries[0] <= queries[1] < arr.length
  

思路

        由于是范围查询，比较自然而然能想到的方法是前缀和。我们先抛开本题的异或操作，想想如何是求nums数组的下标[begin, end]范围的和，是怎么使用前缀和来求解的。假如直接累加，那么每次的时间复杂度都是O(end - begin)，由于这个范围最大可以到n，这样每次时间复杂度都是O(n)。使用前缀和的思路，我们可以先预处理一个pre[]数组，pre表示nums数组中前i个元素的和，特殊的，pre[0]由于表示的是前0个元素的和，并不存在，可以固定为0。有个这个前缀和的数组，我们在盘算下标[begin, end]范围的和的时间，可以直接使用 pre[end+1] - pre[begin]，这样，每次查询的时间复杂度就降低到了O(1)。
        回到本题，可以跟前缀和类似，采取前缀异或，然后使用2个前缀异或就可以快速求得区间异或的结果。由于异或操作也符合结合律和互换律，我们可以推导如下。

1. xor[begin, end] = nums[begin] ^ nums[begin + 1] ^ ... ^ nums[end]
2.                 = nums[begin] ^ nums[begin + 1] ^ ... ^ nums[end] ^ 0
3.                = nums[begin] ^ nums[begin + 1] ^ ... ^ nums[end] ^ (nums[0] ^ nums[0] ^ ... ^ nums[begin-1] ^ nums[begin-1])
4.                = (nums[0] ^ ... ^ nums[begin-1]) ^ (nums[0] ^ ... ^ nums[end])
5.                = pre[begin] ^ pre[end+1]

复制代码

图解

代码

1. public int[] xorQueries(int[] arr, int[][] queries) {
2.    int n = arr.length;
3.    int[] pre = new int[n + 1];
4.    for (int i = 0; i < n; i++) {
5.        pre[i+1] = pre[i] ^ arr[i];
6.    }
7.    int[] ans = new int[queries.length];
8.    for (int i = 0; i < queries.length; i++) {
9.        ans[i] = pre[queries[i][1] + 1] ^ pre[queries[i][0]];
10.    }
11.    return ans;
12. }

复制代码

耗时

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。