LeetCode 1310. 子数组异或查询 Java/C++ 前缀和-一一网

【摘要】 Java/C++ 前缀和
链接：https://leetcode-cn.com/problems/xor-queries-of-a-subarray/solution/javac-qian-zhui-he-by-oyzg-wtva/ 解题思路
利用异或具有 x^x = 0；的特点用数组encoded记录从头异或到arr[i-1]的结果 [l,r]的异或结果就等于 …

Java/C++ 前缀和

链接：https://leetcode-cn.com/problems/xor-queries-of-a-subarray/solution/javac-qian-zhui-he-by-oyzg-wtva/
解题思路

利用异或具有 x^x = 0；的特点
用数组encoded记录从头异或到arr[i-1]的结果
[l,r]的异或结果就等于 [1,l-1]¹的结果因为前l-1个数都异或了2次，就抵消了

代码：
java：

class Solution { public int[] xorQueries(int[] arr, int[][] queries) { int n = arr.length;
		int m = queries.length;
		int[] encoded = new int[n+1];
		for(int i = 1; i <= n; i++) { encoded[i] = encoded[i-1]^arr[i-1];
		}
		int[] res = new int[m];
		for(int i = 0; i < n; i++) { res[i] = encoded[queries[i][0]]^encoded[queries[i][1]+1];
		}
		return res; }
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15

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

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16