不会写代码怎么做网站,软件开发的三种基本方法,普通人怎么样做网站,市场营销策划方案案例思路#xff1a;树上每个节点存储拥有该节点的数组元素的最小值#xff0c;left节点表示0#xff0c;right节点表示1#xff0c;构建完成后遍历树当子节点没有比mi小的元素时直接输出-1#xff0c;否则向下构造。
struct tree{int m;tree*leftnullptr,*rightnullptr;tree…
思路树上每个节点存储拥有该节点的数组元素的最小值left节点表示0right节点表示1构建完成后遍历树当子节点没有比mi小的元素时直接输出-1否则向下构造。
struct tree{int m;tree*leftnullptr,*rightnullptr;tree(int valINT_MAX):m(val){}
};
class Solution {tree*rootnew tree;void add(int val){tree*curroot;for(int i31;i0;i--){if(1ival){if(!cur-right) cur-rightnew tree(val);else cur-right-mmin(val,cur-right-m);curcur-right;}else{if(!cur-left) cur-leftnew tree(val);else cur-left-mmin(val,cur-left-m);curcur-left;}}}int find(int val,int tar){int x0;tree*curroot;for(int i31;i0;i--){if(1ival){if(cur-leftcur-left-mtar) x|1i,curcur-left;else if(cur-rightcur-right-mtar) curcur-right;else return -1;}else {if(cur-rightcur-right-mtar) x|1i,curcur-right;else if(cur-leftcur-left-mtar) curcur-left;else return -1;}}return x;}
public:vectorint maximizeXor(vectorint nums, vectorvectorint queries) {//sort(nums.begin(),nums.end());for(int i:nums) add(i);vectorint 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 cnt0;tree*children[2]{nullptr,nullptr};
};
class Solution {tree*root;void add(int val){tree*curroot;for(int i31;i0;i--){int indexvali1;if(!cur-children[index]) {cur-children[index]new tree;}curcur-children[index];cur-cnt;}}int find(int val,int m){int x0;tree*curroot;for(int i31;i0;i--){int indexvali1;if(mi1){if(cur-children[index]) xcur-children[index]-cnt;if(!cur-children[index^1]) return x;curcur-children[index^1];}else {if(!cur-children[index]) return x;curcur-children[index];}}return xcur-cnt;}int f(vectorint nums,int x){rootnew tree;int res0;for(int i1;inums.size();i){add(nums[i-1]);resfind(nums[i],x);}return res;}
public:int countPairs(vectorint nums, int low, int high) {return f(nums,high)-f(nums,low-1);}
};
