Key points of algorithm:
- 01Trie
- reference resources: 01Trie
- Offline query and online query
- 01some statistical information of subtree can be additionally maintained in trie node
$1 title
Title Link
Title Description
Give you an array of nonnegative integers, nums. There is also a query array queries, where queries[i] = [xi, mi].
The answer to the ith query is the maximum value obtained by bitwise XOR (XOR) of xi and any element in the num array that does not exceed mi. In other words, the answer is max (Num [J] XOR xi), where all j satisfy num [J] < = mi. If all elements in nums are greater than mi, the final answer is - 1.
Returns 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.
Tips: 1 <= nums.length, queries.length <= 1e5 queries[i].length == 2 0 <= nums[j], xi, mi <= 1e9
Sample
Example 1:
Input: num = [0,1,2,3,4], queries = [[3,1], [1,3], [5,6]]
Output: [3,3,7]
Explanation:
- 0 and 1 are the only two integers that do not exceed 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The greater of the two is 3.
- 1 XOR 2 = 3.
- 5 XOR 2 = 7.
Example 2:
Input: num = [5,2,4,6,6,3], queries = [[12,4], [8,1], [6,3]]
Output: [15, - 1,5]
$2 solution
If mi is not exceeded, the problem becomes to find the maximum XOR value for a given xi. This is a basic problem solved by 01Trie, which can be referred to 01Trie This article.
Algorithm: 01Trie + offline query
Given all the query questions directly, we can use the idea of offline, that is, reasonably adjust the order of answering queries, so as to reduce the time complexity.
Sort all numbers of nums, and then sort the query q = (x, m) from small to large by M
Enumeration query qi = (xi, mi). First, insert all numbers less than or equal to mi in num into 01Trie. This process can maintain a pointer on num and insert only the part after the pointer. After the insertion is completed, the maximum XOR value of the inserted number in xi and 01Trie is the answer to the query.
code
Note: if the following code changes the dictionary tree definition Trie01 *trie = Trie01() to Trie01 trie, and changes trie01 - > insert() and trie01 - > search() to trie01 Insert() and trie01 Search(), the running time will and time out, which is increased by 4 times after testing.
Dictionary tree direct use 01Trie Templates in.
struct Query
{
int idx;
int xi;
int mi;
Query(int i, int xi, int mi):idx(i),xi(xi),mi(mi){}
bool operator<(const Query& q) const
{
return mi < q.mi;
}
};
class Solution {
public:
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
int m = queries.size();
sort(nums.begin(), nums.end());
vector<Query> qs;
for(int i = 0; i < m; ++i)
qs.emplace_back(i, queries[i][0], queries[i][1]);
sort(qs.begin(), qs.end());
Trie01 *trie01 = new Trie01();
vector<int> result(m);
int iter = 0;
for(int j = 0; j < m; ++j)
{
while(iter < n && nums[iter] <= qs[j].mi)
{
trie01 -> insert(nums[iter]);
++iter;
}
result[qs[j].idx] = trie01 -> search(qs[j].xi);
}
return result;
}
};
Algorithm: 01Trie + online query
On the basis of conventional 01Trie, add a minx field to the node to represent the minimum value of the number on the subtree with the node as the root. This information is needed when processing queries online.
First insert all numbers into 01Trie, and then process each query in turn.
For each query q[i] = (xi, mi), find the value with the largest XOR with xi in the built Trie01. The process is as follows:
Start from the root and go to the leaves iter Maintenance process
current iter It should always be a guarantee iter -> minx <= mi Yes, you need to judge at this time iter Which direction should I go
if xi The current bit of is 1:
You'd better go to the left subtree: If there is a left subtree, go to the left subtree, otherwise go to the right subtree
if xi The current bit of is 0:
You'd better go to the right subtree: There is a right subtree, and the minimum value of the right subtree <= miļ¼Then go to the right subtree, otherwise go to the left subtree
code
Trie01 needs to be modified on the basis of the conventional template. The code is as follows
struct Trie01Node
{
Trie01Node *left, *right;
int minx;
Trie01Node(int minx=INT_MAX)
{
left = nullptr, right = nullptr;
this -> minx = minx;
}
~Trie01Node(){}
};
class Trie01
{
public:
Trie01()
{
root = new Trie01Node();
}
~Trie01()
{
if(root)
{
delete_subtree(root);
}
}
void insert(int num)
{
Trie01Node *iter = root;
iter -> minx = min(iter -> minx, num);
// Enumeration from high to low
for(int i = 30; i >= 0; --i)
{
if((num >> i) & 1)
{
if(!iter -> right)
iter -> right = new Trie01Node();
iter = iter -> right;
}
else
{
if(!iter -> left)
iter -> left = new Trie01Node();
iter = iter -> left;
}
iter -> minx = min(iter -> minx, num);
}
}
bool empty() const
{
if(!root)
return true;
if(!root -> left && !root -> right)
return true;
return false;
}
int search(int x, int mi)
{
if(empty())
return -1;
/*
* Given x, find a that maximizes x ^ a
* Try to make the x on the high position different from a
* All the numbers are 30 in length
*/
Trie01Node *iter = root;
if(iter -> minx > mi)
return -1;
int a = 0;
for(int i = 30; i >= 0; --i)
{
if((x >> i) & 1)
{
if(iter -> left)
iter = iter -> left;
else
{
iter = iter -> right;
a |= (1 << i);
}
}
else
{
if(iter -> right && iter -> right -> minx <= mi)
{
iter = iter -> right;
a |= (1 << i);
}
else
iter = iter -> left;
}
}
return a ^ x;
}
private:
Trie01Node *root;
void delete_subtree(Trie01Node* node)
{
if(node -> left)
delete_subtree(node -> left);
if(node -> right)
delete_subtree(node -> right);
delete node;
node = nullptr;
}
};
class Solution {
public:
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
int m = queries.size();
Trie01 *trie01 = new Trie01();
for(int x: nums) trie01 -> insert(x);
vector<int> result(m);
for(int i = 0; i < m; ++i)
{
result[i] = trie01 -> search(queries[i][0], queries[i][1]);
}
return result;
}
};