【力扣：1707 1803】0-1字典树

本文主要是介绍【力扣：1707 1803】0-1字典树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：树上每个节点存储拥有该节点的数组元素的最小值，left节点表示0，right节点表示1，构建完成后遍历树当子节点没有比mi小的元素时直接输出-1，否则向下构造。

struct tree{int m;tree*left=nullptr,*right=nullptr;tree(int val=INT_MAX):m(val){}
};
class Solution {tree*root=new tree;void add(int val){tree*cur=root;for(int i=31;i>=0;i--){if(1<<i&val){if(!cur->right) cur->right=new tree(val);else cur->right->m=min(val,cur->right->m);cur=cur->right;}else{if(!cur->left) cur->left=new tree(val);else cur->left->m=min(val,cur->left->m);cur=cur->left;}}}int find(int val,int tar){int x=0;tree*cur=root;for(int i=31;i>=0;i--){if(1<<i&val){if(cur->left&&cur->left->m<=tar) x|=1<<i,cur=cur->left;else if(cur->right&&cur->right->m<=tar) cur=cur->right;else return -1;}else {if(cur->right&&cur->right->m<=tar) x|=1<<i,cur=cur->right;else if(cur->left&&cur->left->m<=tar) cur=cur->left;else return -1;}}return x;}
public:vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {//sort(nums.begin(),nums.end());for(int i:nums) add(i);vector<int> res;for(auto& i:queries){res.push_back(find(i[0],i[1]));}return res;}
};

思路：已知nums[i],nums[j]异或值应在[low,high]之间，因而可以转化为小于high的数量减去小于low-1的数量，将问题转化为两个数的异或值小于target的数量，所以树的节点应该记录该节点下元素的数量，然后按位构造当target的此位是0的时候不能构造为1，当target的此位是1时可以构造为0或1，可以直接加上0节点下元素数量，然后向1处接着构造，这样累加之后就得到了异或值小于target的数量

struct tree{int cnt=0;tree*children[2]={nullptr,nullptr};
};
class Solution {tree*root;void add(int val){tree*cur=root;for(int i=31;i>=0;i--){int index=val>>i&1;if(!cur->children[index]) {cur->children[index]=new tree;}cur=cur->children[index];cur->cnt++;}}int find(int val,int m){int x=0;tree*cur=root;for(int i=31;i>=0;i--){int index=val>>i&1;if(m>>i&1){if(cur->children[index]) x+=cur->children[index]->cnt;if(!cur->children[index^1]) return x;cur=cur->children[index^1];}else {if(!cur->children[index]) return x;cur=cur->children[index];}}return x+cur->cnt;}int f(vector<int>& nums,int x){root=new tree;int res=0;for(int i=1;i<nums.size();i++){add(nums[i-1]);res+=find(nums[i],x);}return res;}
public:int countPairs(vector<int>& nums, int low, int high) {return f(nums,high)-f(nums,low-1);}
};

这篇关于【力扣：1707 1803】0-1字典树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---