力扣421 数组中两个数的最大异或值 Trie模板题 一种新的写法

https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/

class Solution {
    class Trie {
        private Trie nxt[] = new Trie[2];

        public void insert(int num) {
            Trie p = this;    //直接将当前对象当作头节点

            for (int i = 30; i >= 0; --i) {
                /* 将所有数字都化为30位二进制数，先插入最高位 */
                int b = (num >> i) & 1;
                if (p.nxt[b] == null) {
                    p.nxt[b] = new Trie();
                }
                p = p.nxt[b];
            }
            /* 因为所有序列都是30位的，所以不需要标注序列是否结尾了 */
        }

        public int find(int num) {
            //找到和num异或后最大的数
            Trie p = this;
            int ret = 0;

            for (int i = 30; i >= 0; --i) {
                int b = (num >> i) & 1;

                if (p.nxt[1 - b] != null) {
                    //要使异或值最大，则最好与num在该位取相反值
                    b = 1 - b;
                }
                p = p.nxt[b];

                ret = ret * 2 + b;
            }

            return ret;
        }
    }

    public int findMaximumXOR(int[] nums) {
        Trie root = new Trie();
        int ans = 0;

        for (int num : nums) {
            root.insert(num);
        }

        for (int num : nums) {
            ans = Math.max(ans, num ^ root.find(num));
        }

        return ans;
    }
}