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

题目：

题解：

const highBit = 30type trie struct {left, right *trie
}func (t *trie) add(num int) {cur := tfor i := highBit; i >= 0; i-- {bit := num >> i & 1if bit == 0 {if cur.left == nil {cur.left = &trie{}}cur = cur.left} else {if cur.right == nil {cur.right = &trie{}}cur = cur.right}}
}func (t *trie) check(num int) (x int) {cur := tfor i := highBit; i >= 0; i-- {bit := num >> i & 1if bit == 0 {// a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走if cur.right != nil {cur = cur.rightx = x*2 + 1} else {cur = cur.leftx = x * 2}} else {// a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走if cur.left != nil {cur = cur.leftx = x*2 + 1} else {cur = cur.rightx = x * 2}}}return
}func findMaximumXOR(nums []int) (x int) {root := &trie{}for i := 1; i < len(nums); i++ {// 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中root.add(nums[i-1])// 将 nums[i] 看作 ai，找出最大的 x 更新答案x = max(x, root.check(nums[i]))}return
}func max(a, b int) int {if a > b {return a}return b
}