LeetCode 1829中等字典树 · 位运算
每个查询的最大异或值 图解题解
这道题到底在问什么
给定升序非负整数数组 nums 和整数 maximumBit。做 n 次查询:每次选一个满足 0 ≤ k 且 k 的二进制不超过 maximumBit 位的整数 k,使 k 和当前数组全部元素的异或值最大,把 k 记入答案;然后删掉数组最后一个元素。按顺序返回所有 k。
- 输入
- nums=[0,1,1,3], maximumBit=2
- 输出
- [0,3,2,3]
- 输入
- nums=[2,3,4,7], maximumBit=3
- 输出
- [5,2,6,5]
最优解：一步一步想明白
- 3记牢两句话:第一,每次答案 k = xs 异或 mask,其中 xs 是当前总异或、mask 是 maximumBit 位全 1;第二,删掉末尾那个数 v,只要 xs 异或 v 就能同步更新总异或。下面每一帧都在套这两条。
- 4先把 mask 定下来。maximumBit 是 3,mask 就是 2 的 3 次方减 1,等于 7,二进制是 111,三位全是 1,它是 k 能取到的最大值,也是每次能顶到的最大异或值。舞台上这排是 nums = [2, 3, 4, 7],接下来先把它们全部异或起来,得到初始的总异或 xs。
- 5把 nums[0] = 2 异或进总异或。上一步 xs 是 0,二进制 000,和 2 的二进制 010 逐位比较,同位相同得 0、不同得 1,结果是 010,也就是 2。现在 xs 更新成 2。
- 6把 nums[1] = 3 异或进总异或。上一步 xs 是 2,二进制 010,和 3 的二进制 011 逐位比较,同位相同得 0、不同得 1,结果是 001,也就是 1。现在 xs 更新成 1。
- 7把 nums[2] = 4 异或进总异或。上一步 xs 是 1,二进制 001,和 4 的二进制 100 逐位比较,同位相同得 0、不同得 1,结果是 101,也就是 5。现在 xs 更新成 5。
- 8把 nums[3] = 7 异或进总异或。上一步 xs 是 5,二进制 101,和 7 的二进制 111 逐位比较,同位相同得 0、不同得 1,结果是 010,也就是 2。现在 xs 更新成 2。
- 9四个数全异或完了,总异或 xs = 2,二进制 010。手边现在有两样东西:总异或 xs = 2,还有 mask = 7。下面开始逐个查询,每次都用这两样算出答案 k。
- 10再把核心想清楚。我们要让 xs 异或 k 最大,最大能有多大?每一位都变成 1,就是 mask。想让某一位变 1,k 在那一位就取和 xs 相反的值,合起来 k 就是 xs 异或 mask。代回去,xs 异或 k 等于 xs 异或 xs 异或 mask,前两个 xs 抵消,只剩 mask,正好顶满。而且这样的 k 一定在 0 到 mask 之间,是合法的选择。所以每次查询的答案就是 k = xs 异或 mask。
- 11第 0 次查询。舞台上灰掉的是前几轮已经删掉的,还亮着的这 4 个数就是当前数组,它们的总异或 xs = 2,二进制 010。下一步用 xs 和 mask 算这次的 k。
- 12套公式,k = xs 异或 mask = 2 异或 7。二进制是 010 异或 111,逐位取反得到 101,也就是 5。验证一下,把这个 k 和 xs 异或回去,010 异或 101 等于 111,正好是 mask,顶满了。把 5 记进答案,现在是 [5]。
- 13这次查询做完,按题意删掉末尾元素 nums[3] = 7,标红的就是它。总异或不用重算,异或自己是自己的逆运算,把 xs 异或这个 7 就等于把它剔出去:2 异或 7 等于 5。数组缩短一格,带着新的 xs = 5 进下一次查询。
- 14第 1 次查询。舞台上灰掉的是前几轮已经删掉的,还亮着的这 3 个数就是当前数组,它们的总异或 xs = 5,二进制 101。下一步用 xs 和 mask 算这次的 k。
- 15套公式,k = xs 异或 mask = 5 异或 7。二进制是 101 异或 111,逐位取反得到 010,也就是 2。验证一下,把这个 k 和 xs 异或回去,101 异或 010 等于 111,正好是 mask,顶满了。把 2 记进答案,现在是 [5、2]。
- 16这次查询做完,按题意删掉末尾元素 nums[2] = 4,标红的就是它。总异或不用重算,异或自己是自己的逆运算,把 xs 异或这个 4 就等于把它剔出去:5 异或 4 等于 1。数组缩短一格,带着新的 xs = 1 进下一次查询。
- 17第 2 次查询。舞台上灰掉的是前几轮已经删掉的,还亮着的这 2 个数就是当前数组,它们的总异或 xs = 1,二进制 001。下一步用 xs 和 mask 算这次的 k。
- 18套公式,k = xs 异或 mask = 1 异或 7。二进制是 001 异或 111,逐位取反得到 110,也就是 6。验证一下,把这个 k 和 xs 异或回去,001 异或 110 等于 111,正好是 mask,顶满了。把 6 记进答案,现在是 [5、2、6]。
- 19这次查询做完,按题意删掉末尾元素 nums[1] = 3,标红的就是它。总异或不用重算,异或自己是自己的逆运算,把 xs 异或这个 3 就等于把它剔出去:1 异或 3 等于 2。数组缩短一格,带着新的 xs = 2 进下一次查询。
- 20第 3 次查询。舞台上灰掉的是前几轮已经删掉的,还亮着的这 1 个数就是当前数组,它们的总异或 xs = 2,二进制 010。下一步用 xs 和 mask 算这次的 k。
- 21套公式,k = xs 异或 mask = 2 异或 7。二进制是 010 异或 111,逐位取反得到 101,也就是 5。验证一下,把这个 k 和 xs 异或回去,010 异或 101 等于 111,正好是 mask,顶满了。把 5 记进答案,现在是 [5、2、6、5]。
- 22这次查询做完,按题意删掉末尾元素 nums[0] = 2,标红的就是它。总异或不用重算,异或自己是自己的逆运算,把 xs 异或这个 2 就等于把它剔出去:2 异或 2 等于 0。数组清空,xs = 0,所有查询都答完了。
- 23四次查询都答完了,回放一遍:每次都是拿当轮的总异或 xs 异或 mask 得到 k,分别是 5、2、6、5,删末尾就顺手把那个数从 xs 里异或掉。最终答案数组是 [5、2、6、5]。总异或只算一次,之后每次查询都是常数时间。
⚠️ 容易写错的地方
✗ 错：把答案记成了最大异或值 mask,而不是选出的 k
✓ 对：答案数组存的是 k = xs ⊕ mask
题目要的是那个使异或最大的 k;最大异或值恒等于 mask、对每次查询都一样,存它就全错了
✗ 错：每次查询都从头重算总异或,复杂度退化到 O(n²)
✓ 对：删末尾 v 时用 xs ⊕= v 增量更新
异或自反,一个数异或两次等于没异或,xs 异或掉被删的 v 就等价于从总异或里去掉它,O(1) 完成
✗ 错：mask 写成了 2^maximumBit,多算了一位
✓ 对：mask = 2^maximumBit − 1
k 只能占 maximumBit 位,mask 应是这 maximumBit 位全 1,即 2^maximumBit 减 1;多的那一位超出了 k 的合法范围
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
from string import *
from operator import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
ans = []
xs = reduce(xor, nums)
for x in reversed(nums):
k = 0
for i in range(maximumBit - 1, -1, -1):
if (xs >> i & 1) == 0:
k |= 1 << i
ans.append(k)
xs ^= x
return ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
int xs = 0;
for (int& x : nums) {
xs ^= x;
}
int n = nums.size();
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
int x = nums[n - i - 1];
int k = 0;
for (int j = maximumBit - 1; ~j; --j) {
if ((xs >> j & 1) == 0) {
k |= 1 << j;
}
}
ans[i] = k;
xs ^= x;
}
return ans;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public int[] getMaximumXor(int[] nums, int maximumBit) {
int n = nums.length;
int xs = 0;
for (int x : nums) {
xs ^= x;
}
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
int x = nums[n - i - 1];
int k = 0;
for (int j = maximumBit - 1; j >= 0; --j) {
if (((xs >> j) & 1) == 0) {
k |= 1 << j;
}
}
ans[i] = k;
xs ^= x;
}
return ans;
}
}复杂度
时间
O(n · b)
n 是数组长度,b 是 maximumBit。先扫一遍算总异或 O(n);n 次查询,每次逐位构造 k 是 O(b),删末尾更新 xs 是 O(1)。b 是很小的常数(通常不超过 20 位),所以整体等价于 O(n)
空间
O(1)
只用了 xs、k 这几个整数变量,额外空间是常数。答案数组长度 n 是题目必需的输出,通常不计入额外空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 每个查询的最大异或值 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题的最大异或值为什么和数组内容几乎无关,总是 mask?+
因为真正决定上限的是 k 的自由度,不是 xs 具体等于几。k 可以取 0 到 mask 之间任意值,而 mask 是 maximumBit 位全 1。不管 xs 长什么样,我都能让 k 在每一位取 xs 的相反位,这样 xs 异或 k 每一位都是 1,正好等于 mask。所以最大异或值恒为 mask,变化的只是为了达到它而选的那个 k = xs 异或 mask。
每次删掉末尾元素,为什么不用重新遍历就能维护总异或?+
靠的是异或的自反性:一个数异或它自己等于 0,一个数异或 0 等于它自己。当前总异或 xs 里已经把末尾元素 v 异或进去了,现在要把 v 拿掉,只要再异或一次 v,它就和原来那次成对抵消,相当于从没进来过。所以一句 xs 异或 v 就完成删除,O(1)。这和前缀和里减掉一个数是同一种思路,只是把加减换成了异或。
如果反过来是每次删掉最前面的元素,做法要怎么改?+
思路完全不变,还是维护当前总异或 xs、每次答案取 xs 异或 mask,只是删的对象从末尾换成开头,更新时改成 xs 异或掉最前面那个元素即可。异或删除不挑位置,谁被删就异或谁。本题恰好删末尾,配合逆序遍历最顺手;删开头就正序遍历、每步异或掉当前首元素。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 每个查询的最大异或值 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。