中小企业网站功能模块及数据库表,东莞建筑公司都有哪些,河北电子网站建设,flash网站教程题目
给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries #xff0c;其中 queries[i] [xi, mi] 。
第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元素按位异或#xff08;XOR#xff09;得到的最大值。换句话说#xff0c;答案是 max(nums[j] XO…题目
给你一个由非负整数组成的数组 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] 解释
0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 3 而 1 XOR 3 2 。二者中的更大值是 3 。1 XOR 2 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]mi1即可。
字典树
因为nums[j]的取值范围为0 nums[j], xi, mi 109所以我们只需要将nums[j]的后30位取出来构造字典树即可从根节点到叶子节点代表从高位到低位Trie[] childrennew Trie[2]代表下一位是否可以取0或者1例如下标0为null的话证明下一位不能为0。所以找最大的异或结果的话可以通过从根节点开始尽量走一些使得当前位异或结果为1的路径因为根节点到叶子节点是从高位到低位的所以优先选择使得异或高位为1
代码
class Solution {public int[] maximizeXor(int[] nums, int[][] queries) {int nqueries.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 cur0;Trie root new Trie();Arrays.sort(nq,(o1, o2) - o1[1]-o2[1]);for (int i 0; i n; i) {while (curnums.lengthnums[cur]nq[i][1]){root.add(nums[cur]);cur;}res[nq[i][2]]cur0?-1:root.get(nq[i][0]);}return res;}
}
public class Trie{static final int h30;Trie[] childrennew Trie[2];void add(int val){Trie nodethis;for (int ih-1;i0;i--){int cur(vali)1;if(node.children[cur]null){node.children[cur]new Trie();}nodenode.children[cur];}}int get(int val){Trie nodethis;int res0;for (int ih-1;i0;i--){int t(vali)1;if(node.children[t^1]!null){res|1i;t^1;}nodenode.children[t];}return res;}}
