异或运算的性质:
例题1: lc2425. 所有数对的异或和
运用到的性质: 1,2,3,4
数组 A = [a,b]
数组 B = [c,d,e]
答案 ans = (a^c)^(a^d)^(a^e) ^ (b^c) ^(b^d)^(b^e)
整理以后得 : (a^a^a)^(b^b^b) ^(c^c)^(d^d)^(e^e)
由性质2可知, a^a=0, a^0=a
故奇数次数的为本身,偶数次数的为0
代码为:
class Solution {
public int xorAllNums(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int ans = 0;
for(int i=0;i<n;i++){
ans^=m%2==0?0:nums1[i];
}
for(int i=0;i<m;i++){
ans^=n%2==0?0:nums2[i];
}
return ans;
}
}
例题2:lc2433. 找出前缀异或的原始数组
设数组A = [a,b,c,d,e,f]
则 设异或前缀和为 B
B[0] = a
B[1] = a^b
B[2] = a^b^c
B[3] = a^b^c^d
B[4] = a^b^c^d^e
B[5] = a^b^c^d^e^f
设答案为C数组
由异或的性质可知
C[5] = B[5]^B[4] = (a^b^c^d^e^f)^( a^b^c^d^e)
= (a^a)^(b^b)^(c^c)^(d^d)^(e^e)^f = f
C[4] = B[4]^B[3] = (a^b^c^d^e)^( a^b^c^d)
= (a^a)^(b^b)^(c^c)^(d^d) ^e = e
C[3] = B[3]^B[2] = (a^b^c^d)^( a^b^c)
= (a^a)^(b^b)^(c^c)^d = d
C[2] = B[2]^B[1] = (a^b^c)^( a^b)
= (a^a)^(b^b)^c = c
C[1] = B[1]^B[0] = (a^b)^a
= (a^a)^b = b
C[0] = B[0] = a
class Solution {
public int[] findArray(int[] pref) {
int n = pref.length;
int[] ans = new int[n];
for(int i=n-1;i>=1;i--){
ans[i] = pref[i]^pref[i-1];
}
ans[0] = pref[0];
return ans;
}
}