JIAKAOBO

LeetCode

venmo
wechat

感谢赞助!

  • ㊗️
  • 大家
  • offer
  • 多多！

Problem

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 ≤ i ≤ j < n.

Follow up: Could you do this in O(n) runtime?

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

Input: nums = [0]
Output: 0

Example 3:

Input: nums = [2,4]
Output: 6

Example 4:

Input: nums = [8,10,2]
Output: 10

Example 5:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

Code

class Solution {
    class Node{
        Node[] children;

        public Node(){
            children = new Node[2];
        }
    }

    private Node root;
    private int res;
    public int findMaximumXOR(int[] nums) {
        root = new Node();
        res = Integer.MIN_VALUE;

        for(int num : nums){
            build(num);
        }

        for(int num : nums){
            search(num);
        }

        return res;
    }

    private void search(int num){
        Node node = root;
        int sum = 0;
        for(int i = 31; i >= 0; i--){
            int curr = (num >> i) & 1;
            if(curr == 0) {
                if (node.children[1] != null) {
                    sum += 1 << i;
                    node = node.children[1];
                } else {
                    node = node.children[0];
                }
            } else {
                if(node.children[0] != null) {
                    sum += 1 << i;
                    node = node.children[0];
                } else {
                    node = node.children[1];
                }
            }
        }

        res = Math.max(res, sum);
    }

    private void build(int num){
        Node node = root;

        for(int i = 31; i >= 0; i--){
            // 从高位向地位建树
            int curr = (num >> i) & 1;
            if(node.children[curr] == null){
                node.children[curr] = new Node();
            }

            node = node.children[curr];
        }
    }
}