专栏首页算法修养LeetCode 1803. Count Pairs With XOR in a Range (二叉树)

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;
}
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode Weekly Contest 42解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • Python3刷题系列(九)

    用户5473628
  • C++版 - 剑指Offer 面试题36:数组中的逆序对及其变形(Leetcode 315. Count of Smaller Numbers After Self)题解

    题目:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

    Enjoy233
  • 【LeetCode】数据结构与算法 最短路径

    其实,8-10遍高频效果是最好的,这基本就是到另一个境界了。当然,大家没有那么多时间,3-5遍也可以去面试了。

    程序员小王
  • LeetCode Weekly Contest 35解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 常用算法整理

    王磊-AI基础
  • 二叉树问题(二)-LeetCode 965、563、993、958、919(树深度,层次遍历)

    如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。 只有给定的树是单值二叉树时,才返回 true;否则返回 false。

    算法工程师之路
  • LeetCode笔记:Weekly Contest 241 比赛记录

    如上一个博客所述,这周的比赛其实因为一些琐事没能参加,只是赛后做了一下比赛的题目,这里就大致记录一下吧。

    codename_cys
  • 剑指offer【50~59】

    排序数组,很明显二分查找,找到第一个 >= k 的元素索引以及第一个 > k 的元素索引,两者相减即为答案,即 lowerBound - upperBound。...

    echobingo
  • 【leetcode刷题】T136-二叉搜索树中的众数

    https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/

    木又AI帮
  • 第二轮 Python 刷题笔记一:数组

    经过四十多天缓慢的刷题,现在进度大概是刷了八十多道 LeetCode 题,最近也在吸取过来人的经验,仍然需要对刷题计划进行调整。

    TTTEED
  • LeetCode刷题记录(easy难度1-20题)

    leetcode刷题记录 本文记录一下leetcode刷题记录,记录一下自己的解法和心得。

    earthchen
  • 【leetcode刷题】T146-二叉树的层平均值

    https://leetcode-cn.com/problems/average-of-levels-in-binary-tree

    木又AI帮
  • Python3刷题系列(四)

    https://leetcode.com/problems/happy-number/

    用户5473628
  • LeetCode 297:二叉树的序列化与反序列化 Serialize and Deserialize Binary Tree

    序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重...

    爱写bug
  • LeetCode 230. 二叉搜索树中第K小的元素(中序遍历)

    给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

    Michael阿明
  • Data Structurestackheapheap的实现索引堆tree并查集图 Graph

    堆的基本性质: ①堆中的某一个节点总是不小于或不大于其父节点的值。 ②堆总是一棵完全二叉树 比较经典的堆有二叉堆,费波纳茨堆等等。如果一棵二叉树最下层上的...

    西红柿炒鸡蛋
  • Js算法与数据结构拾萃(4):二叉树

    因此只要答对这道题,你就可以超越世界级大牛,问鼎码林之巅(逃) 导读: •二叉树知识重点•二叉树深度不一,因此天生适用递归,因此可用递归处理•判断两树相等•翻转...

    一粒小麦
  • ​LeetCode刷题实战132:分割回文串 II

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈

扫码关注云+社区

领取腾讯云代金券