每日一题_1310.子数组异或查询

leetcode每日一题

image.png

• 注意：如果是暴力做法的话，是会超时的，应该考虑异或的性质
  • 性质1： ,
  • 性质2：
  • 异或通常都是使用异或和来解决问题，观察下图可以建立如下prefix(前缀数组)
    
    image.png

便可以得到如下代码

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        vector<int > res;
        int len=arr.size(); 
        int prefix[30000+5]; 
        
        int tmp=0;
        for (int i=0; i<len; ++i) prefix[i]=tmp^=arr[i];

        len=queries.size();
        for (int i=0; i<len; ++i)
            for (int j=0; j<2; j+=2) res.push_back(arr[queries[i][j]] ^ prefix[queries[i][j]] ^ prefix[queries[i][j+1]]);

        return res;
    }
};