深圳专业做网站专业公司手机上怎么做网站

1. 题目

给定数组 A（下标从0到n-1，n为数组长度），和一个查询列表。
每一项查询包括两个整数 i 和 k。
对于每次查询，计算Ai, A(i + 1), ..., A(i+k-1)的异或值。结果保存在列表中。

样例1
输入: A = [1,2,3,4] and query = [(0,2),(1,2)]
输出: [3,1]
解释:
1 ^ 2 = 3
2 ^ 3 = 1样例2
输入: A = [1,2,4,8] and query = [(0,3),(1,3)]
输出: [7,14]
解释:
1 ^ 2 ^ 4 = 7
2 ^ 4 ^ 8 = 14注意事项
在大部分编程语言中你可以使用 '^'来进行异或运算。
数组长度小于1000，查询次数小于1000。
保证Ai<1000,k>0,i+k-1<n。

2. 解题

• 计算前缀异或值
• 放了方便边界处理，前后各加一个0，0与其他异或不改变别人
• 对区间两端点的前缀异或值异或，即得到区间内元素的异或值

/*** Definition of Interval:* classs Interval {*     int start, end;*     Interval(int start, int end) {*         this->start = start;*         this->end = end;*     }* }*/class Solution {
public:vector<int> intervalXOR(vector<int> &A, vector<Interval> &query) {int s = 0;A.insert(A.begin(),0);A.push_back(0);for(int i = 0; i < A.size(); ++i){s ^= A[i];A[i] = s;}vector<int> ans;for(int i = 0; i < query.size(); ++i){ans.push_back(A[query[i].start]^A[query[i].start+query[i].end]);}return ans;}
};

100% 数据通过测试
总耗时 50 ms
您的提交打败了 96.69% 的提交!