easy understanding C++ program and clear explanation


  • 0
    F
    struct node{
    		bool val;
    		node *left,*right;
    		node(){
    			left=NULL;
    			right=NULL;
    		}
    	};
    	//this is the function to inset number to a trie
    	//the left child represent "1",right child represents "0"
    	void insert(node *root,int num,int d){
    		if(d==0) return;
    		int flag=num&d;
    		if(flag==d){//if we meet "1",then go right
    			if(root->right==NULL) root->right=new node;
    			root=root->right;
    			insert(root,num,d/2);
    		}else{//if we meet "0",then go left
    			if(root->left==NULL) root->left=new node;
    			root=root->left;
    			insert(root,num,d/2);
    		}
    	}
    
    	//find the other number that make the max XOR result
    	//It is just the opposite way of inserting,cause we want to find the max result of XOR
    	void compare(node *root,int num,int d,vector<int> &s){
    		if(d==0) return;
    		int flag=num&d;
    		if(flag==d){
    		//if we meet "1", we consider left child first,if the node has left child,it means we got a "1" bit in result and go left.
    		//if the node doesn't have left child ,we got a "0" bit in result and go right
    			if(root->left!=NULL){
    				s.push_back(1);
    				root=root->left;
    			}else if(root->right!=NULL){
    				s.push_back(0);
    				root=root->right;
    			}
    			compare(root,num,d/2,s);
    		}else{//just oppositely
    			if(root->right!=NULL){
    				s.push_back(1);
    				root=root->right;
    			}else if(root->left!=NULL){
    				s.push_back(0);
    				root=root->left;
    			}
    			compare(root,num,d/2,s);
    		}
    	}
    
    
    int findMaximumXOR(vector<int>& nums) {
    		//max_nums is the max number among nums 
            int max_nums=0;
    		for(int i=0;i<nums.size();i++){
    			if(nums[i]>max_nums) max_nums=nums[i];
    		}
    		//find the first "1" in max_nums(from left to right) and d represents that number
    		long long dd=1;
    		while((double)max_nums/dd>=1){
    			dd*=2;
    		}
    		int d=dd/2;
    		node *root=new node;
    		//create a trie for all the numbers
    		for(int i=0;i<nums.size();i++){
    			insert(root,nums[i],d);
    		}
    		int max=0;
    		//for each number in trie, we find the other number that make the max XOR result
    		for(int i=0;i<nums.size();i++){
    			vector<int> s;//store every bit of the max XOR result
    			int max_temp=0;
    			compare(root,nums[i],d,s);//to find the other number that make the max XOR result
    			for(int i=0;i<s.size();i++){//change the max result to decimal
    				max_temp=max_temp+pow(2.0,(s.size()-i-1)*1.0)*s[i];
    			}
    			if(max_temp>max) max=max_temp;
    		}
    		return max;
        }
    

Log in to reply
 

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