在Python中查找每个查询的最大XOR的程序

假设我们有一个预排序的数组nums，大小为n，还有一个值b。 我们要执行以下查询n次 –

• 查找一个非负值k，使得nums中的所有元素和k的异或最大，其中k <2 ^ m。所以k是第i个查询的答案。

• 从当前数组nums中删除最后一个元素。

• 我们必须查找一个数组答案，其中answer[i]是第i个查询的答案。

因此，如果输入类似于nums = [0,1,1,3]，m = 2，则输出将为[0,3,2,3]，因为

• nums = [0,1,1,3]，k = 0，因为0 XOR 1 XOR 1 XOR 3 XOR 0 = 3。

• nums = [0,1,1]，k = 3，因为0 XOR 1 XOR 1 XOR 3 = 3。

• nums = [0,1]，k = 2，因为0 XOR 1 XOR 2 = 3。

• nums = [0]，k = 3，因为0 XOR 3 = 3。

为了解决这个问题，我们将执行以下步骤 –

• x：=2 ^ m – 1

• 对于i从0到nums大小-1，执行以下操作 –

  • nums [i]：= nums [i] XOR x

  • x：= nums [i]

• 返回颠倒后的nums

示例

让我们看以下实现以更好地理解 –

def solve(nums, m):
   x=2**m-1
   for i in range(len(nums)):
      nums[i] ^= x
      x = nums[i]
   return(nums[::-1])

nums = [0,1,1,3]
m = 2
print(solve(nums, m))

输入

[0,1,1,3]，2

输出

[0, 3, 2, 3]