当前位置:网站首页>力扣解法汇总558- 四叉树交集
力扣解法汇总558- 四叉树交集
2022-07-22 08:55:00 【失落夏天】
目录链接:
力扣编程题-解法汇总_分享+记录-CSDN博客
GitHub同步刷题项目:
https://github.com/September26/java-algorithms
原题链接:力扣
描述:
二进制矩阵中的所有元素不是 0 就是 1 。
给你两个四叉树,quadTree1 和 quadTree2。其中 quadTree1 表示一个 n * n 二进制矩阵,而 quadTree2 表示另一个 n * n 二进制矩阵。
请你返回一个表示 n * n 二进制矩阵的四叉树,它是 quadTree1 和 quadTree2 所表示的两个二进制矩阵进行 按位逻辑或运算 的结果。
注意,当 isLeaf 为 False 时,你可以把 True 或者 False 赋值给节点,两种值都会被判题机制 接受 。
四叉树数据结构中,每个内部节点只有四个子节点。此外,每个节点都有两个属性:
val:储存叶子结点所代表的区域的值。1 对应 True,0 对应 False;
isLeaf: 当这个节点是一个叶子结点时为 True,如果它有 4 个子节点则为 False 。
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
}
我们可以按以下步骤为二维区域构建四叉树:
如果当前网格的值相同(即,全为 0 或者全为 1),将 isLeaf 设为 True ,将 val 设为网格相应的值,并将四个子节点都设为 Null 然后停止。
如果当前网格的值不同,将 isLeaf 设为 False, 将 val 设为任意值,然后如下图所示,将当前网格划分为四个子网格。
使用适当的子网格递归每个子节点。
如果你想了解更多关于四叉树的内容,可以参考 wiki 。
四叉树格式:
输出为使用层序遍历后四叉树的序列化形式,其中 null 表示路径终止符,其下面不存在节点。
它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val] 。
如果 isLeaf 或者 val 的值为 True ,则表示它在列表 [isLeaf, val] 中的值为 1 ;如果 isLeaf 或者 val 的值为 False ,则表示值为 0 。
示例 1:
输入:quadTree1 = [[0,1],[1,1],[1,1],[1,0],[1,0]]
, quadTree2 = [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
输出:[[0,0],[1,1],[1,1],[1,1],[1,0]]
解释:quadTree1 和 quadTree2 如上所示。由四叉树所表示的二进制矩阵也已经给出。
如果我们对这两个矩阵进行按位逻辑或运算,则可以得到下面的二进制矩阵,由一个作为结果的四叉树表示。
注意,我们展示的二进制矩阵仅仅是为了更好地说明题意,你无需构造二进制矩阵来获得结果四叉树。
示例 2:
输入:quadTree1 = [[1,0]]
, quadTree2 = [[1,0]]
输出:[[1,0]]
解释:两个数所表示的矩阵大小都为 1*1,值全为 0
结果矩阵大小为 1*1,值全为 0 。
示例 3:
输入:quadTree1 = [[0,0],[1,0],[1,0],[1,1],[1,1]]
, quadTree2 = [[0,0],[1,1],[1,1],[1,0],[1,1]]
输出:[[1,1]]
示例 4:
输入:quadTree1 = [[0,0],[1,1],[1,0],[1,1],[1,1]]
, quadTree2 = [[0,0],[1,1],[0,1],[1,1],[1,1],null,null,null,null,[1,1],[1,0],[1,0],[1,1]]
输出:[[0,0],[1,1],[0,1],[1,1],[1,1],null,null,null,null,[1,1],[1,0],[1,0],[1,1]]
示例 5:
输入:quadTree1 = [[0,1],[1,0],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
, quadTree2 = [[0,1],[0,1],[1,0],[1,1],[1,0],[1,0],[1,0],[1,1],[1,1]]
输出:[[0,0],[0,1],[0,1],[1,1],[1,0],[1,0],[1,0],[1,1],[1,1],[1,0],[1,0],[1,1],[1,1]]
提示:
quadTree1 和 quadTree2 都是符合题目要求的四叉树,每个都代表一个 n * n 的矩阵。
n == 2^x ,其中 0 <= x <= 9.
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/logical-or-of-two-binary-grids-represented-as-quad-trees
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
* 解题思路: * 一道递归的题目,如果两个节点任意一个isLeaf为true,如果val=1使用其自身,否则使用另外一个。因为1|0或者1|1都为1。而0的话为输入值。 * 如果两个节点的isLeaf都为false,则递归判断,得出结果后修改返回节点的isLeaf和val。 * 这里要注意的是,判断四个值是否一致应该是a==b&b==c&c==d,而不是a==b==c==d。我就是这问题查了三个多小时
代码:
public Node intersect(Node quadTree1, Node quadTree2) {
if (quadTree1.isLeaf) {
if (quadTree1.val) {
return quadTree1;
}
return quadTree2;
}
if (quadTree2.isLeaf) {
if (quadTree2.val) {
return quadTree2;
}
return quadTree1;
}
Node node = new Node();
node.topLeft = intersect(quadTree1.topLeft, quadTree2.topLeft);
node.topRight = intersect(quadTree1.topRight, quadTree2.topRight);
node.bottomLeft = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
node.bottomRight = intersect(quadTree1.bottomRight, quadTree2.bottomRight);
//是否全一致
node.isLeaf = (node.topLeft.isLeaf & node.topRight.isLeaf & node.bottomRight.isLeaf & node.bottomLeft.isLeaf) && (node.topLeft.val == node.topRight.val) && (node.topRight.val == node.bottomLeft.val)&& (node.bottomLeft.val == node.bottomRight.val);
node.val = node.topLeft.val | node.topRight.val | node.bottomRight.val | node.bottomLeft.val;
if (node.isLeaf) {
node.topLeft = null;
node.topRight = null;
node.bottomRight = null;
node.bottomLeft = null;
}
return node;
}
边栏推荐
- QT笔记——eventFilter事件过滤器
- Dokcer running Nacos container automatic exit problem
- fcntl函数
- 「武汉理工大学 软件工程复习」第五章 | 软件体系结构
- QT exe只允许运行单个
- Solve typescript error: a computed property name in an interface must refer to an expression why type
- 一招教你招聘数据可视化~还有人不会这些数据分析小案例吗?
- 小程序实现列表和详情页
- Reversible information hiding method of image in ciphertext domain based on fine-grained embedding space reservation
- Research on vulnerability identification technology for project version differences
猜你喜欢
Inscription des femmes
qt5.12 + vs2019 无法定位程序输入点 于动态链接库
Reentrant function
SQL多条件查询无法实现
How to solve the gloomy life under the middle-aged crisis of it
如何破解IT中年危机下的惨淡人生
QT notes - vs generating multiple exe files for a project
Understanding of continue in C language (fishing_1)
What level do programmers need to reach to get 20K monthly salary without pressure?
主动降噪耳机排行榜10强,主动降噪耳机十大品牌
随机推荐
Gbase8s database minus operator
MySQL密码正确但是启动报错Unable to create initial connections of pool.Access denied for user ‘root‘@‘localhost
Qt|编辑框的使用总结
Use of bullets in object pool mode in aircraft war
SQL多条件查询无法实现
3.Transbot修改显示分辨率
Maintenance of gbase8s database constraint mode
Gbase8s database restrictions on set collection
43. String multiplication
Web3 sharing
QT笔记——QJson
2021-10-18使用eop烧写裸板程序
Gbase8s database set database object mode statement
反射+注解+泛型
「武汉理工大学 软件工程复习」第六章 | 编码规范
基于混合深度学习的多类型低速率DDoS攻击检测方法
文件描述符的复制
Gbase8s database set collection statement
QT exe只允许运行单个
Distsql deep parsing: creating a dynamic distributed database