E.位运算-异或：异或消消乐入门（1720题+2433题+2683题）

题目链接1720. 解码异或后的数组简单算法原理解法位运算异或消消乐1ms击败100.00%时间复杂度O(N)思路很简单根据“异或消消乐”的原理a^a0用ai表示原始中数组的第i个数⬇️由于encoded[0]a1^a2因此此题中原始的a2encoded[0]^firsta1^a2^a1a2类似的我们可以递推推导出其余数JAVA代码class Solution { //1720. 解码异或后的数组 public int[] decode(int[] encoded, int first) { //异或消消乐 int nencoded.length; int[] retnew int[n1]; ret[0]first; for(int i1;in1;i) ret[i]encoded[i-1]^ret[i-1]; return ret; } }题目链接2433. 找出前缀异或的原始数组中等算法原理解法位运算异或消消乐2ms击败66.25%时间复杂度O(N)观察题述中的规律拿示例一举例⬇️pref[0]5因此ret[0]5pref[1]5^72因此ret[1]pref[0]^pref[1](5)^(5)^77pref[2]5^7^20因此ret[2]pref[1]^pref[2](5^7)^(5^7)^22pref[3]5^7^2^33因此ret[3]pref[2]^pref[3](5^7^2)^(5^7^2)^33pref[4]5^7^2^3^21因此ret[4]pref[3]^pref[4](5^7^2^3)^(5^7^2^3)^22因此ret[i]pref[i-1]^pref[i]JAVA代码class Solution { //2433. 找出前缀异或的原始数组 public int[] findArray(int[] pref) { int npref.length; int[] retnew int[n]; ret[0]pref[0]; for(int i1;in;i) ret[i]pref[i-1]^pref[i]; return ret; } }题目链接2683. 相邻值的按位异或中等算法原理解法脑筋急转弯异或消消乐2ms击败100.00%时间复杂度O(N)可能很多小伙伴都会去想怎么模拟这个过程但其实根本没必要我们观察示例1能够发现如果这个原始数组真的存在那么derived数组中所有值异或在一起的值为original[0]^original[1]^^original[1]^original[2]^original[2]^original[0]0如果不存在则必然结果不为0因此我们仅需将derived数组中所以数异或在一起判断最终结果是否为0即可JAVA代码class Solution { //2683. 相邻值的按位异或 public boolean doesValidArrayExist(int[] derived) { int ret0; for(int x:derived) ret^x; return ret0; } }