leetcode421. Maximum XOR of Two Numbers in an Array

    public int findMaximumXOR(int[] nums) {
        //32位到第i位为止算出的异或最大值
        int maxResult = 0;
        int mask = 0;
        for(int i = 31 ; i>=0 ; i--) {
            //i~32位全为1
            mask |= (1 << i);
            Set<Integer> set = new HashSet<>();
            //取所有整数的前32-i位的结果并保存
            for(int num : nums) {
                set.add(num | mask);
            }
            
            //假设第i位能够异或出结果1
            int greedyTry = maxResult | (1 << i);
            //使用结论a^b=c,则a^c=b。根据该结论，我们假设整数数组中的两个整数在第i为的值为1，且set中存储了所有的a的值，异或出b的值后看b是否也在set中。
            for(int num : set) {
                if(set.contains(greedyTry ^ num)) {
                    maxResult = greedyTry;
                    break;
                }
            }
        }
        return maxResult;

    }

    public int findMaximumXOR2(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        //将所有整数存入Trie结构
        TrieNode root = new TrieNode(-1);
        for (int i = 0; i < nums.length; i += 1) {
            addToTrie(root, nums[i]);
        }
        return findMaximum(root, 31);
    }
    
    private int findMaximum(TrieNode node, int pos) {
        if (pos == 0) {
            return 0;
        }
        
        //表明在第pos位上只有1，异或结果一定为0
        if (node.zero == null) {
            return findMaximum(node.one, pos - 1);
        }
        //表明在第pos上只有0，异或结果一定为0
        if (node.one == null) {
            return findMaximum(node.zero, pos - 1);
        }
        return findMaximum(node.zero, node.one, pos - 1);
    }
    
    private int findMaximum(TrieNode node1, TrieNode node2, int pos) {
        //计算第pos上的异或结果
        int result = (node1.val ^ node2.val) << pos;
        //pos==0代表为叶节点
        if (pos == 0) {
            return result;
        }
        //获取node1的可用子节点和node2的可用子节点
        TrieNode next1 = null;
        TrieNode next2 = null;
        if (node1.zero != null && node1.one == null) {
            next1 = node1.zero;
        } else if (node1.zero == null && node1.one != null) {
            next1 = node1.one;
        }
        if (node2.zero != null && node2.one == null) {
            next2 = node2.zero;
        } else if (node2.zero == null && node2.one != null) {
            next2 = node2.one;
        }
        //满足node1和node2均只有一个子节点，将二者进行迭代比较
        if (next1 != null && next2 != null) {
            return result + findMaximum(next1, next2, pos - 1);
        }
        //node1不为空代表node1只有一个可用子节点，如果子节点为0，则选node2的one子节点，否则选node2的zero子节点
        if (next1 != null) {
            if (next1.val == 0) {
                next2 = node2.one;
            } else {
                next2 = node2.zero;
            }
            return result + findMaximum(next1, next2, pos - 1);
        }
        //同上
        if (next2 != null) {
            if (next2.val == 0) {
                next1 = node1.one;
            } else {
                next1 = node1.zero;
            }
            return result + findMaximum(next1, next2, pos - 1);
        }
        //node1和node2均有两个子节点，则将node1.one和node2.zero 与 node1.zero和node2.one进行比较得出最大异或值
        return result + Math.max(findMaximum(node1.zero, node2.one, pos - 1), findMaximum(node1.one, node2.zero, pos - 1));
    }
    
    private void addToTrie(TrieNode root, int x) {
        TrieNode curr = root;
        int[] binary = toBinary(x);
        for (int i = 0; i < binary.length; i += 1) {
            if (binary[i] == 0) {
                if (curr.zero == null) {
                    curr.zero = new TrieNode(0);
                }
                curr = curr.zero;
            } else {
                if (curr.one == null) {
                    curr.one = new TrieNode(1);
                }
                curr = curr.one;
            }
        }
    }
    
    private int[] toBinary(int x) {
        int[] result = new int[31];
        for (int i = 30; i >= 0; i -= 1) {
            result[i] = x & 1;
            x >>= 1;
        }
        return result;
    }
    
    static class TrieNode {
        int val;
        TrieNode zero;
        TrieNode one;
        
        public TrieNode(int val) {
            this.val = val;
            zero = null;
            one = null;
        }
    }