E.位运算-异或：1829. 每个查询的最大异或值

题目链接1829. 每个查询的最大异或值中等算法原理解法位运算前缀异或2ms击败100.00%时间复杂度O(N)通过观察题目给的示例发现每个最终的最大值是唯一的最大值是max(1maximumBIt)-1假设xor是前缀异或的最终结果那么我们就需要找到答案k使得xor^kmax两边同时^xor得到kxor^max接下来就要处理每次填写时删除末尾元素的细节了我们发现从左往右遍历数组的时候前缀越来越长第1轮只看前1个元素→正好对应最后一个位置第2轮看前2个→正好对应倒数第2个位置第3轮前3个→正好对应倒数第3个位置第4轮前4个→正好对应倒数第4个位置……因此我们仅需在正序遍历的同时计算k逆序填回结果数组即可~JAVA代码class Solution { //1829. 每个查询的最大异或值 public int[] getMaximumXor(int[] nums, int maximumBit) { int nnums.length; int[] retnew int[n]; int max(1maximumBit)-1;//找到最大值 int xor0;//存储异或结果 int indexn-1; for(int x:nums){ xor^x; ret[index--]xor^max; } return ret; } }