题目描述
思路解析动画文字版
记住「高位优先、能相反就相反」:异或的高位拉开差距最划算,所以每个数都尽量去匹配一个高位与它相反的数。下面先建树、再查询,逐帧套它。
插入 3:第 1 位 0 → 节点 0
插入 3:第 2 位 1 → 节点 01
插入 3:第 3 位 1 → 节点 011
插入 5:第 1 位 1 → 节点 1
插入 5:第 2 位 0 → 节点 10
插入 5:第 3 位 1 → 节点 101
插入 6:第 1 位 1 → 节点 1
插入 6:第 2 位 1 → 节点 11
插入 6:第 3 位 0 → 节点 110
字典树建好:3 个数各走出一条根到叶的路径
查询 3:第 1 位想走 1 → 成功,这位记 1
查询 3:第 2 位想走 0 → 成功,这位记 1
查询 3:第 3 位想走 0 → 失败,这位记 0
数 3 的最佳异或 = 6;ans = 6
查询 5:第 1 位想走 0 → 成功,这位记 1
查询 5:第 2 位想走 1 → 成功,这位记 1
查询 5:第 3 位想走 0 → 失败,这位记 0
数 5 的最佳异或 = 6;ans = 6
查询 6:第 1 位想走 0 → 成功,这位记 1
查询 6:第 2 位想走 0 → 失败,这位记 0
查询 6:第 3 位想走 1 → 成功,这位记 1
数 6 的最佳异或 = 5;ans = 6
答案:最大异或 = 6
边界:单个数答案 0;0 正常参与;全相同则异或为 0。
两个高频追问:可用逐位+哈希前缀替代字典树;位宽是常数所以接近线性。
参考代码
from typing import Listclass Solution: def findMaximumXOR(self, nums: List[int]) -> int: root = {} for x in nums: node = root for b in range(31, -1, -1): bit = (x >> b) & 1 node = node.setdefault(bit, {}) ans = 0 for x in nums: node = root cur = 0 for b in range(31, -1, -1): bit = (x >> b) & 1 want = bit ^ 1 if want in node: cur |= 1 << b node = node[want] else: node = node[bit] ans = max(ans, cur) return ans复杂度
- 时间:O(32n),建树:n 个数各走 32 位;查询:n 个数各走 32 位。位宽 32 是常数,整体相当于 O(n)
- 空间:O(32n),字典树最多 32n 个节点(每个数最坏新建一条 32 层的路径)
易错点
面试追问把动画讲成自己的话
追问除了字典树,还有别的解法吗?
追问为什么时间能做到接近线性?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
删除子文件夹
LeetCode 1233 · 中等 · 沿着 字典树套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题