This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

The title

You are given an array of non-negative integers, nums. Queries [I] = [xi, mi]

The answer to the i-th query is the maximum value obtained by bitwise XOR for xi and any element in the numS array that does not exceed mi. In other words, the answer is Max (nums[j] XOR xi), where all j satisfies nums[j] <= mi. If all elements in nums are greater than mi, the final answer is -1.

Return an integer array answer as the answer to the query, where answer.length == queries.length and answer[I] is the answer to the ith query.

Example 1:

Input: nums =,1,2,3,4 [0], the queries = [[3, 1], [1, 3], [5, 6]] output:,3,7 [3] :

  1. 0 and 1 are the only two integers that do not exceed 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The greater value of the two is 3.
  2. 1 XOR 2 = 3.
  3. 5 XOR 2 = 7.

Example 2:

Input: nums =,2,4,6,6,3 [5], the queries = [[12, 4], [8, 1], [6]] output: (15, 1, 5)

Their thinking

  • Query array queries[I] = [xi, mi], sort by m, and record the original location of each query.
  • Nums [cur]<=mi, nums[0…cur] <=mi, nums[0…cur] < mi Therefore, after traversing a query [I] = [xi, mi], the next traversal only needs to move the cur pointer to num[cur]<=mi+1.

The dictionary tree

Nums [j] = 0 <= nums[j], xi, mi <= 109, so we only need to extract the last 30 bits of nums[j] to construct a dictionary tree, from the root node to the leaf node, representing from high to low. Trie[] children=new Trie[2] indicates whether the next digit can be 0 or 1. For example, if the subscript 0 is null, the next digit cannot be 0. Therefore, to find the maximum xOR result, we can start from the root node and try to take some paths that make the current xor result 1. Since the root node and the leaf node are from the high to the low, the xOR high is preferentially selected as 1

code

class Solution {

    public int[] maximizeXor(int[] nums, int[][] queries) {

        int n=queries.length;
        int[] res = new int[n];
        int[][] nq = new int[n][3];
        Arrays.sort(nums);

        for (int i = 0; i < n; i++) {
            nq[i][0]=queries[i][0];
            nq[i][1]=queries[i][1];
            nq[i][2]=i;
        }
        int cur=0;
        Trie root = new Trie();
        Arrays.sort(nq,(o1, o2) -> o1[1]-o2[1]);
        for (int i = 0; i < n; i++) {
            while (cur<nums.length&&nums[cur]<=nq[i][1])
            {
                root.add(nums[cur]);
                ++cur;
            }
            res[nq[i][2]]=cur==0? -1:root.get(nq[i][0]);
        }
        returnres; }}public class Trie{
       static final int h=30;
        Trie[] children=new Trie[2];
        void add(int val){
            Trie node=this;
            for (int i=h-1; i>=0; i--){int cur=(val>>i)&1;
                if(node.children[cur]==null)
                {
                    node.children[cur]=newTrie(); } node=node.children[cur]; }}int get(int val){
            Trie node=this;
            int res=0;
            for (int i=h-1; i>=0; i--){int t=(val>>i)&1;
                if(node.children[t^1]! =null){
                    res|=1<<i;
                    t^=1;
                }
                node=node.children[t];

            }
            returnres; }}Copy the code