给你一个由非负整数组成的数组 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]
提示:
1 <= nums.length, queries.length <= 10^5
queries[i].length == 2
0 <= nums[j], xi, mi <= 10^9
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-xor-with-an-element-from-array 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
参考文章:字符串匹配算法(Trie树)
MIN
字段,记录子树中最小的数,将数字的各个二进制位插入trie树,查找的时候走相反的位的路线(如果存在的话)class trie{ // 在线处理
public:
trie* next[2] = {NULL,NULL};
int MIN = INT_MAX;
void insert(int n){
trie *cur = this;
cur->MIN = min(cur->MIN, n);
for(int i = 31; i >= 0; --i)
{
int bit = (n>>i)&1;
if(!cur->next[bit])
cur->next[bit] = new trie();
cur = cur->next[bit];
cur->MIN = min(cur->MIN, n);
}
}
int getMaxXOR(int n, int limit)
{
trie *cur = this;
if(cur->MIN > limit) return -1;
int res = 0;
for(int i = 31; i >= 0; --i)
{
int bit = (n>>i)&1;
if(cur->next[bit^1] && cur->next[bit^1]->MIN <= limit)
{
res |= 1<<i;
bit ^= 1;
}
cur = cur->next[bit];
}
return res;
}
};
class Solution {
public:
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
trie *t = new trie();
for(auto n : nums)
t->insert(n);
vector<int> ans(queries.size());
for(int i = 0; i < queries.size(); ++i)
{
int num = queries[i][0], limit = queries[i][1];
ans[i] = t->getMaxXOR(num, limit);
}
return ans;
}
};
936 ms 261 MB C++
我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!