LeetCode最大的异或

剑指 Offer II 067. 最大的异或

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

输入：nums = [3,10,5,25,2,8] 输出：28 解释：最大运算结果是 5 XOR 25 = 28.

来源:LeetCode

利用字典树进行解题。

将每个元素转换成二进制位，从高到底依次表现在字典树上，然后对字典树就行搜索

当遇到节点是0的时候，由于进行异或操作，下一个最好选择1； 当遇到节点是1的时候，由于进行异或操作，下一个最好选择0；

由于将元素转换成二进制，所以只可能是0或者1，所以该字典树是一个二叉树。

当前是左侧节点，当往右孩子节点走，那就加上层数2+1，否则就是x2； 当前是右侧节点，当往左孩子节点走，那就加上层数2+1，否则就是x2；

最后返回res。

当然首先要定义一个字典树的类。

class Solution {

    Trie root=new Trie();
    static final int high_bit=30;
    public int findMaximumXOR(int[] nums) {

        int len=nums.length,max=0;
        int res=0;
        for(int i=1;i=0;i--)
        {
            int bit=(num>>i) & 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;
            }
        }
    } 
    public int check(int num)
    {
        int res=0;
        Trie cur=root;
        for(int i=high_bit;i>=0;i--){
            int bit=(num>>i) & 1;
            if(bit==0)
            {
                if(cur.right!=null)
                {
                    cur=cur.right;
                    res=res*2+1;
                }
                else{
                    cur=cur.left;
                    res=res*2;
                }
            }
            else{
                if(cur.left!=null)
                {
                    cur=cur.left;
                    res=res*2+1;
                }
                else{
                    cur=cur.right;
                    res=res*2;
                }
            }
        }
        return res;
    }    
}
class Trie{
        Trie left=null;
        Trie right=null;
    }