A new way to use trie to solve it buy build a recursion function to return answer


  • 0
    Y
    class node
    {
        int val=0;
        node[] to=new node[2];
        void add(int x,int mx)
        {
            node now=this;
            for(int i=mx;i>=0;i--)
            {
                int v=(x>>i)&1;
                if(now.to[v]==null) now.to[v]=new node();
                now=now.to[v];
            }
            now.val++;
        }
        int match(int x,int mx)
        {
            node now=this;
            int r=0;
            for(int i=mx;i>=0;i--)
            {
                int v=(x>>i)&1;
                if(now.to[v^1]!=null) 
                {
                    now=now.to[v^1];
                    r|=1<<i;
                }else now=now.to[v];
            }
            return r;
        }
        boolean can(int x)
        {
            return to[x]!=null;
        }
    }
    
    public class Solution {
        int max(int x,int y){
            return x>y?x:y;
        }
        int dfs(node a,node b,int d)
        {
            if(d==0)
            {
                return a.can(0)&&b.can(1) ||(a.can(1)&&b.can(0)) ?1:0;
            }
            int l=0,r=1;
            int ans=-1,in=0;
            if(a.can(0)&&b.can(1))ans=max(ans,dfs(a.to[0],b.to[1],d-1)|(1<<d));
            if(a.can(1)&&b.can(0)) ans=max(ans,dfs(a.to[1],b.to[0],d-1)|(1<<d));
            if(ans==-1)
            {
                if(a.can(0)&&b.can(0))ans=max(ans,dfs(a.to[0],b.to[0],d-1));
                if(a.can(1)&&b.can(1)) ans=max(ans,dfs(a.to[1],b.to[1],d-1));
            }
            return ans;
        }
        public int findMaximumXOR(int[] nums) {
            if(nums.length==1) return 0;
            int mx=-1,xo=0,n=nums.length;
            for(int i=0;i<n;i++)
            xo|=nums[i];
            for(int i=30;i>=0;i--)
            if(((xo>>i)&1)==1)
            {
                mx=i;
                break;
            }
            if(mx==-1) return 0;
            node head=new node();
            for(int i=0;i<n;i++) head.add(nums[i],mx);
              int ans=0;
           
            return dfs(head,head,mx);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.