題目

給你一個由非負整數組成的數組 nums 。另有一個查詢數組 queries ，其中 queries[i] = [xi, mi] 。

第 i 個查詢的答案是 xi 和任何 nums 數組中不超過 mi 的元素按位異或（XOR）得到的最大值。換句話說，答案是 max(nums[j] XOR xi) ，其中所有 j 均滿足 nums[j] <= mi 。如果 nums 中的所有元素都大于 mi，最終答案就是 -1 。

返回一個整數數組 answer 作為查詢的答案，其中 answer.length == queries.length 且 answer[i] 是第 i 個查詢的答案。

示例 1：

輸入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
輸出：[3,3,7]
解釋：

1. 0 和 1 是僅有的兩個不超過 1 的整數。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。
2. 1 XOR 2 = 3.
3. 5 XOR 2 = 7.
   示例 2：

輸入：nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
輸出：[15,-1,5]

解題思路

• 將查詢數組queries[i] = [xi, mi]，按照m進行排序，并且記錄下原來每個查詢所在的位置。
• 將nums數組也進行排序，這樣的話，只需要每一個查詢維護一個單調遞增的指針cur即可，滿足nums[cur]<=mi,而nums[0…cur]里面的元素也是小于mi的，因為排序以后的查詢數組的mi是遞增的，所以每遍歷完一個查詢queries[i] = [xi, mi]，下一個遍歷只需要把cur指針移動至滿足num[cur]<=mi+1即可。

字典樹

因為nums[j]的取值范圍為0 <= nums[j], xi, mi <= 109，所以我們只需要將nums[j]的后30位取出來構造字典樹即可，從根節點到葉子節點，代表從高位到低位，Trie[] children=new Trie[2]代表下一位是否可以取0或者1，例如下標0為null的話，證明下一位不能為0。所以找最大的異或結果的話，可以通過從根節點開始，盡量走一些使得當前位異或結果為1的路徑，因為根節點到葉子節點是從高位到低位的，所以優先選擇使得異或高位為1

代碼

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]);}return res;}
}    
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]=new Trie();}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];}return res;}}