Leetcode 421 FineMaxXOR

public class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];//字母表映射
        isEnd = false;
    }

    //插入字符串 
	//我们从字典树的根开始,插入字符串。对于当前字符对应的子节点,有两种情况 
	//子节点存在。沿着指针移动到子节点,继续处理下一个字符。 
	//子节点不存在。创建一个新的子节点,记录在children数组的对应位置上,
    //然后沿着指针移动到子节点,继续搜索下一个字符。 
    public void insert(String word) {
        Trie node = this;//root 

        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';

            if (node.children[index] == null)
                node.children[index] = new Trie();

            node = node.children[index];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }
    
	//查找前缀 
	//我们从字典树的根开始,查找前缀。对于当前字符对应的子节点,有两种情况 
	//子节点存在:沿着指针移动到子节点,继续搜索下一个字符,直到isEnd = true
	//子节点不存在:说明字典树中不包含该前缀,返回null。 
    private Trie searchPrefix(String prefix) {
        Trie node = this;

        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';

            if (node.children[index] == null)
                return null;

            node = node.children[index];
        }
        return node;
    }
}

class Solution {
        // 字典树的根节点
        Trie root = new Trie();
        // 最高位的二进制位编号为 30
        static final int HIGH_BIT = 30;

        public int findMaximumXOR(int[] nums) {
            int n = nums.length;
            int x = 0;
            for (int i = 1; i < n; ++i) {
                // 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中
                add(nums[i - 1]);
                // 将 nums[i] 看作 a_i，找出最大的 x 更新答案
                x = Math.max(x, check(nums[i]));
            }
            return x;
        }

        public void add(int num) {
            Trie cur = root;
            for (int k = HIGH_BIT; k >= 0; --k) {
                int bit = (num >> k) & 1;
                if (bit == 0) {
                    if (cur.left == null) {
                        cur.left = new Trie();
                    }
                    cur = cur.left;
                } else {
                    if (cur.right == null) {
                        cur.right = new Trie();
                    }
                    cur = cur.right;
                }
            }
        }

    	//尽可能找异位 ,  0 ⊕ 1 = 1 , 使得值为最大
        public int check(int num) {
            Trie cur = root;
            int x = 0;
            for (int k = HIGH_BIT; k >= 0; --k) {
                int bit = (num >> k) & 1;
                if (bit == 0) {
                    // a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走
                    if (cur.right != null) {
                        cur = cur.right;
                        x = x * 2 + 1;
                    } else {
                        cur = cur.left;
                        x = x * 2;
                    }
                } else {
                    // a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走
                    if (cur.left != null) {
                        cur = cur.left;
                        x = x * 2 + 1;
                    } else {
                        cur = cur.right;
                        x = x * 2;
                    }
                }
            }
            return x;
        }
    }
}

class Trie {
    Trie left = null;//0
    Trie right = null;//1
}