[LeetCode] 1310. XOR Queries of a Subarray #1310

grandyang · 2019-05-30T16:34:30Z

You are given an array arr of positive integers. You are also given the array queries where queries[i] = [lefti, righti].

For each query i compute the XOR of elements from lefti to righti (that is, arr[lefti] XOR arr[lefti + 1] XOR ... XOR arr[righti] ).

Return an array answer where answer[i] is the answer to the ith query.

Example 1:

Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8]
Explanation:
The binary representation of the elements in the array are:
1 = 0001
3 = 0011
4 = 0100
8 = 1000
The XOR values for queries are:
[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

Example 2:

Input: arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
Output: [8,0,4,4]

Constraints:

1 <= arr.length, queries.length <= 3 * 104
1 <= arr[i] <= 109
queries[i].length == 2
0 <= lefti <= righti < arr.length

这道题给了一个正整数数组，和一堆查询区间，让计算每个区间内所有的数字的'异或'和。博主看到这种玩区间的题目，首先想到的是建立累加和数组，但是这里不是求区间和，而是区间内数字的'异或'和，所以需要研究一下这种这种思路是否在这里同样适用。这里的'异或'是位操作，简单来说就是相同取0，不同取1，根据这个性质可以得出两个结论，第一个结论是相同的数字'异或'后为0，因为相同的数字每一位都是相同的，'异或'后均为0。第二个结论是任何数字'异或'0之后均为其本身不变，因为0'异或'0还是0，0'异或'1后仍为1，并不发生任何变化。

理解了这两条性质后，再来研究下区间，若原数组为 [a, b, c, d]，若想求 c^d，可不可以通过整个区间的'异或'和 a^b^c^d，和前两个数字的'异或' a^b 来得到呢，其实是可以的，将二者'异或'起来，变成 a^b^c^d^a^b，调整下顺序，变为 a^a^b^b^c^d，根据之前分析的性质可以得到 c^d。所以这道题还是可以使用累加和数组的思路来做，只不过这里变成了累加'异或'和数组。分析道这里，应该就不难写出代码了，首先建立累加'异或'和数组，这里长度为 n+1，方便处理边界，对于每个给定区间 [i, j] 的'异或'和计算方法，就是用 xors[j+1]^xors[i] 即可，参见代码如下：

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        int n = arr.size();
        vector<int> res, xors(n + 1);
        for (int i = 1; i <= n; ++i) {
            xors[i] = xors[i - 1] ^ arr[i - 1];
        }
        for (auto &query : queries) {
            res.push_back(xors[query[1] + 1] ^ xors[query[0]]);
        }
        return res;
    }
};

Github 同步地址:

#1310

参考资料：

https://leetcode.com/problems/xor-queries-of-a-subarray/

https://leetcode.com/problems/xor-queries-of-a-subarray/discuss/470702/C%2B%2B-Prefix-XORs

https://leetcode.com/problems/xor-queries-of-a-subarray/discuss/470787/JavaC%2B%2BPython-Straight-Forward-Solution

LeetCode All in One 题目讲解汇总(持续更新中...)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

喜欢请点赞，疼爱请打赏❤️~.~