在一个数组里面找到两个数异或的结果在某个范围之内。
这种题目，就要用二叉树，
代码写的又臭又长。。
struct Node
{
int value;
int left;
int right;
int num;
int pos;
}tree[200005];
class Solution {
public:
int hight;
int lower;
int fun(int root, int number, int h, int l, int pos)
{
if(pos==-1 )
return tree[root].num;
int b = number & (1 << pos);
if(b>0) b=1;
int ans = 0;
int l1 = lower & (1 << pos);
int h1 = hight & (1 << pos);
if(l1>0) l1 =1;
if(h1>0) h1 =1;
if (h == 1 && l == 1)
{
ans = tree[root].num;
}
else if (h == 1 && l == 0)
{
if (b == 1 && l1 ==1)
{
ans = fun(tree[root].left, number, h, l, pos - 1);
}
else if (b == 1 && l1 == 0)
{
ans = fun(tree[root].left, number, h, 1, pos - 1) + fun(tree[root].right, number, h, l, pos - 1);
}
else if (b == 0 && l1 == 1)
{
ans = fun(tree[root].right, number, h, l, pos - 1);
}
else if (b == 0 && l1 == 0)
{
ans = fun(tree[root].left, number, h, l, pos - 1) + fun(tree[root].right, number, h, 1, pos - 1);
}
}
else if (h == 0 && l == 1)
{
if (b == 1 && h1 == 1)
{
ans = fun(tree[root].left, number, h, l, pos - 1) + fun(tree[root].right, number, 1, l, pos - 1);
}
else if (b == 1 && h1 == 0)
{
ans = fun(tree[root].right, number, h, l, pos - 1);
}
else if (b == 0 && h1 == 1)
{
ans = fun(tree[root].left, number, 1, l, pos - 1) + fun(tree[root].right, number, h, l, pos - 1);
}
else if (b == 0 && h1 == 0)
{
ans = fun(tree[root].left, number, h, l, pos - 1);
}
}
else if (h == 0 && l == 0)
{
if (h1 == l1 && h1 == 0)
{
if (b == 1)
{
ans = fun(tree[root].right, number, h, l, pos - 1);
}
else if (b == 0)
{
ans = fun(tree[root].left, number, h, l, pos - 1);
}
}
else if (h1 == l1 && h1 == 1)
{
if (b == 1)
{
ans = fun(tree[root].left, number, h, l, pos - 1);
}
else if (b == 0)
{
ans = fun(tree[root].right, number, h, l, pos - 1);
}
}
else if (h1 == 1 && l1 == 0)
{
if (b == 1)
{
ans = fun(tree[root].left, number, h, 1, pos - 1) + fun(tree[root].right, number, 1, l, pos - 1);
}
else if (b == 0)
{
ans = fun(tree[root].left, number, 1, l, pos - 1) + fun(tree[root].right, number, h, 1, pos - 1);
}
}
}
return ans;
}
int pos2;
void init(int root, int p)
{
if (p == 16)
return;
tree[root].left = ++pos2;
tree[root].right = ++pos2;
tree[root].num=0;
init(tree[root].left, p + 1);
init(tree[root].right, p + 1);
}
void init2(int root,int num, int p)
{
tree[root].num++;
if(p==-1)
return;
int b = num &(1<<p);
if(b>0)
{
init2(tree[root].right,num,p-1);
}
else
{
init2(tree[root].left,num,p-1);
}
}
int countPairs(vector<int>& nums, int low, int high)
{
pos2 = 0;
init(0, 0);
hight = high;
lower = low;
int res = 0;
for (int i = 0; i < nums.size(); i++)
{
res += fun(0, nums[i], 0, 0, 14);
init2(0,nums[i],14);
}
return res;
}
};