Python | Leetcode Python题解之第421题数组中两个数的最大异或值

题目：

题解：

class Trie:def __init__(self):# 左子树指向表示 0 的子节点self.left = None# 右子树指向表示 1 的子节点self.right = Noneclass Solution:def findMaximumXOR(self, nums: List[int]) -> int:# 字典树的根节点root = Trie()# 最高位的二进制位编号为 30HIGH_BIT = 30def add(num: int):cur = rootfor k in range(HIGH_BIT, -1, -1):bit = (num >> k) & 1if bit == 0:if not cur.left:cur.left = Trie()cur = cur.leftelse:if not cur.right:cur.right = Trie()cur = cur.rightdef check(num: int) -> int:cur = rootx = 0for k in range(HIGH_BIT, -1, -1):bit = (num >> k) & 1if bit == 0:# a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走if cur.right:cur = cur.rightx = x * 2 + 1else:cur = cur.leftx = x * 2else:# a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走if cur.left:cur = cur.leftx = x * 2 + 1else:cur = cur.rightx = x * 2return xn = len(nums)x = 0for i in range(1, n):# 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中add(nums[i - 1])# 将 nums[i] 看作 ai，找出最大的 x 更新答案x = max(x, check(nums[i]))return x