[leetcode题解]1310. XOR Queries of a Subarray(子数组的异或结果查询)

题目给定一个全是整数的数组

然后会给定很多查询子区间,比如数组长度为10,则查询子区间可以为小于10的任何区间,比如0-1,0-3,2-8,1-9等等。

题目要的结果是把这些子区间中数组元素全部异或起来后得到的结果。

这个题目很简单,一看到此题,就能想到利用异或的特性来解题。这是凌风技术站leetcode题解1310题,简单的数学题。

1.任意一个数异或之后结果为0。

2.0与任何一个数a的异或结果仍未这个数a。

有了这两个结论,代码就出来了。

首先直接在arr中进行处理,从数组下标0开始,一直往后异或累计,arr[i]处存放的就是0-i所有元素的异或值。

这样如果求区间a-b之间元素的异或值,只需要arr[b] ^ arr[a – 1]即可。

因为

arr[b] = arr[0] ^ arr[1] ^ arr[2] ….. ^ arr[b]

arr[a – 1] = arr[0] ^ arr[1] ^ arr[2] … ^ arr[a – 1]

所以arr[b] ^ arr[a] = arr[0] ^ arr[1] ^ arr[2] … ^arr[b] ^ arr[0] ^ arr[1] ^ arr[2] … ^ arr[a – 1]  (a <= b)

可以看到后面的相当于前面0 – a-1的所有元素异或了2次,所有结果变为0。然后0和arr[a – 1…b]子区间的元素异或结果仍为arr[a – 1 … b]子区间元素的异或结果。

则,leetcode题解1310 xor queries of a subarray这个题目的代码如下:

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        int i;
        vector<int> res;
        int st, ed;
        
        /* 本文有iaccepted发表在凌风技术站iaccepted.net *
        /* 更多题解,欢迎访问iaccepted.net/leetcode */
        for (i = 1; i < arr.size(); i++) {
            arr[i] ^= arr[i - 1];
        }
        
        for (i = 0; i < queries.size(); i++) {
            st = queries[i][0];
            ed = queries[i][1];
            if (st >= 1) {
                res.push_back(arr[ed] ^ arr[st - 1]);
            } else {
                res.push_back(arr[ed]);
            }
        }
        
        return res;
    }
};

凌风技术站leetcode题解专栏,leetcode题解1310题,xor queries of a subarray,解题报告如上。

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]1310. XOR Queries of a Subarray(子数组的异或结果查询)

本文链接地址:https://www.iaccepted.net/algorithm/leetcode/248.html

相关文章