1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Trie {
public:
const int L = 30;
Trie* children[2] = {};
int min = INT_MAX;
void insert(int val) {
Trie* node = this;
node->min = std::min(node->min, val);
for (int i = L - 1; i >= 0; --i) {
int bit = (val >> i) & 1;
if (node->children[bit] == nullptr)
node->children[bit] = new Trie();
node = node->children[bit];
node->min = std::min(node->min, val);
}
}
int getMaxXorWithLimit(int val, int limit) {
Trie* node = this;
if (node->min > limit)
return -1;
int ans = 0;
for (int i = L - 1; i >= 0; --i) {
int bit = (val >> i) & 1;
if (node->children[bit ^ 1] != nullptr && node->children[bit ^ 1]->min <= limit) {
ans |= 1 << i;
bit ^= 1;
}
node = node->children[bit];
}
return ans;
}
};
class Solution {
public:
vector<int> maximizeXor(vector<int> &nums, vector<vector<int>> &queries) {
Trie* t = new Trie();
for (int num : nums)
t->insert(num);
const int n = queries.size();
vector<int> ans(n);
for (int i = 0; i < n; ++i)
ans[i] = t->getMaxXorWithLimit(queries[i][0], queries[i][1]);
return ans;
}
};
|