421. Maximum XOR of Two Numbers in an Array

偏难的medium。暴力不可取。

思路比较容易往按位去做上面靠，因为毕竟只有32bit。

如果有人告诉你用trie可以做，再往后就比较容易想到。把每个数的二进制看作字符串，建树之后。

然后对于每个数a，我们可以在O(1)的时间内找到，和他做xor最大的数b。

这个数有个构造方法，就是从高位开始（trie树从root开始），依次让每一位尽量能取到相反的数，使得该为结果为1

后来还看到一种解法，没有使用trie，其核心思路和用trie类似，但是感觉更为复杂，没有详细了解的必要。

type trie struct {
    num int
    ch [2]*trie
}

func findMaximumXOR(nums []int) int {
    root := &trie{}
    for i := 0; i < len(nums); i++ {
        p := root
        for j := 30; j >= 0; j-- {
            c := nums[i] >> j & 1
            if p.ch[c] == nil {
                p.ch[c] = &trie{}
            }
            p = p.ch[c]
        }
        p.num = nums[i]
    }
    ans := -1
    for i := 0; i < len(nums); i++ {
        p := root
        for j := 30; j >= 0; j-- {
            c := nums[i] >> j & 1
            if p.ch[1-c] != nil {
                p = p.ch[1-c]
            } else {
                p = p.ch[c]
            }
        }
        if p.num ^ nums[i] > ans {
            ans = p.num ^ nums[i]
        }
    }
    return ans
}