LeetCode 1803. Count Pairs With XOR in a Range (二叉树)
2021/6/19 23:26:50
本文主要是介绍LeetCode 1803. Count Pairs With XOR in a Range (二叉树),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
在一个数组里面找到两个数异或的结果在某个范围之内。
这种题目,就要用二叉树,
代码写的又臭又长。。
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; } };
这篇关于LeetCode 1803. Count Pairs With XOR in a Range (二叉树)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain