LeetCode 题解工作台
每个查询的最大异或值
给你一个 有序 数组 nums ，它由 n 个非负整数组成，同时给你一个整数 maximumBit 。你需要执行以下查询 n 次： 找到一个非负整数 k maximumBit ，使得 nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k …
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 前缀和
答案摘要
我们先预处理出数组 `nums` 的异或和 ，即 $xs=nums[0] \oplus nums[1] \oplus \cdots \oplus nums[n-1]$。 接下来，我们从后往前枚举数组 `nums` 中的每个元素 ，当前的异或和为 ，我们需要找到一个数 ，使得 $xs \oplus k$ 的值尽可能大，并且 $k \lt 2^{maximumBit}$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 前缀和 题型思路
题目描述
给你一个 有序 数组 nums ，它由 n 个非负整数组成，同时给你一个整数 maximumBit 。你需要执行以下查询 n 次：
- 找到一个非负整数
k < 2maximumBit，使得nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k的结果 最大化 。k是第i个查询的答案。 - 从当前数组
nums删除 最后 一个元素。
请你返回一个数组 answer ，其中 answer[i]是第 i 个查询的结果。
示例 1：
输入：nums = [0,1,1,3], maximumBit = 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 。
示例 2：
输入：nums = [2,3,4,7], maximumBit = 3 输出：[5,2,6,5] 解释：查询的答案如下： 第一个查询：nums = [2,3,4,7]，k = 5，因为 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7。 第二个查询：nums = [2,3,4]，k = 2，因为 2 XOR 3 XOR 4 XOR 2 = 7 。 第三个查询：nums = [2,3]，k = 6，因为 2 XOR 3 XOR 6 = 7 。 第四个查询：nums = [2]，k = 5，因为 2 XOR 5 = 7 。
示例 3：
输入：nums = [0,1,2,2,5,7], maximumBit = 3 输出：[4,3,6,4,6,7]
提示：
nums.length == n1 <= n <= 1051 <= maximumBit <= 200 <= nums[i] < 2maximumBitnums 中的数字已经按 升序 排好序。
解题思路
方法一：位运算 + 枚举
我们先预处理出数组 nums 的异或和 ，即 。
接下来，我们从后往前枚举数组 nums 中的每个元素 ，当前的异或和为 ，我们需要找到一个数 ，使得 的值尽可能大，并且 。
也即是说，我们从 的第 位开始，往低位枚举，如果 的某一位为 ，那么我们就将 的对应位设置为 ，否则我们就将 的对应位设置为 。这样，最终得到的 就是每一次查询的答案。然后，我们将 更新为 ，继续枚举下一个元素。
时间复杂度 ，其中 和 分别是数组 nums 和 maximumBit 的值。忽略答案数组的空间消耗，空间复杂度 。
class Solution:
def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
ans = []
xs = reduce(xor, nums)
for x in nums[::-1]:
k = 0
for i in range(maximumBit - 1, -1, -1):
if (xs >> i & 1) == 0:
k |= 1 << i
ans.append(k)
xs ^= x
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
The candidate effectively applies bit manipulation to constrain the XOR result within the specified limit.
- question_mark
The candidate demonstrates a good understanding of using prefix sums in the context of XOR calculations.
- question_mark
The candidate is able to optimize the problem solution by leveraging sorted input for efficient query processing.
常见陷阱
外企场景- error
Forgetting to apply the bit mask to limit the XOR result to (2^maximumBit - 1).
- error
Inefficiently recalculating XOR values for each query without leveraging the sorted array structure.
- error
Misunderstanding the prefix XOR calculation and failing to compute it correctly for each query.
进阶变体
外企场景- arrow_right_alt
Increase the size of the input array and test the solution's scalability.
- arrow_right_alt
Use a different sorting method and compare the performance with the current approach.
- arrow_right_alt
Apply a different bitwise operation (e.g., AND or OR) and observe the behavior of the solution.