首页 > 编程语言 >#yyds干货盘点# LeetCode程序员面试金典:建立四叉树

#yyds干货盘点# LeetCode程序员面试金典:建立四叉树

时间:2023-09-19 23:31:42浏览次数:54  
标签:Node yyds r0 金典 网格 grid 四叉树 c0 isLeaf

1.简述:

给你一个 n * n 矩阵 grid ,矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。

你需要返回能表示矩阵 grid 的 四叉树 的根结点。

四叉树数据结构中,每个内部节点只有四个子节点。此外,每个节点都有两个属性:

val:储存叶子结点所代表的区域的值。1 对应 True,0 对应 False。注意,当 isLeaf 为 False 时,你可以把 True 或者 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;
}

我们可以按以下步骤为二维区域构建四叉树:

  1. 如果当前网格的值相同(即,全为 0 或者全为 1),将 isLeaf 设为 True ,将 val 设为网格相应的值,并将四个子节点都设为 Null 然后停止。
  2. 如果当前网格的值不同,将 isLeaf 设为 False, 将 val 设为任意值,然后如下图所示,将当前网格划分为四个子网格。
  3. 使用适当的子网格递归每个子节点。

#yyds干货盘点# LeetCode程序员面试金典:建立四叉树_子节点

如果你想了解更多关于四叉树的内容,可以参考 wiki 。

四叉树格式:

你不需要阅读本节来解决这个问题。只有当你想了解输出格式时才会这样做。输出为使用层序遍历后四叉树的序列化形式,其中 null 表示路径终止符,其下面不存在节点。

它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val] 。

如果 isLeaf 或者 val 的值为 True ,则表示它在列表 [isLeaf, val] 中的值为 1 ;如果 isLeaf 或者 val 的值为 False ,则表示值为 0 。

 

示例 1:

#yyds干货盘点# LeetCode程序员面试金典:建立四叉树_子网_02

输入:grid = [[0,1],[1,0]]
输出:[[0,1],[1,0],[1,1],[1,1],[1,0]]
解释:此示例的解释如下:
请注意,在下面四叉树的图示中,0 表示 false,1 表示 True 。

示例 2:

#yyds干货盘点# LeetCode程序员面试金典:建立四叉树_四叉树_03

输入:grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
输出:[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
解释:网格中的所有值都不相同。我们将网格划分为四个子网格。
topLeft,bottomLeft 和 bottomRight 均具有相同的值。
topRight 具有不同的值,因此我们将其再分为 4 个子网格,这样每个子网格都具有相同的值。
解释如下图所示:

2.代码实现:

class Solution {
    public Node construct(int[][] grid) {
        return dfs(grid, 0, 0, grid.length, grid.length);
    }

    public Node dfs(int[][] grid, int r0, int c0, int r1, int c1) {
        boolean same = true;
        for (int i = r0; i < r1; ++i) {
            for (int j = c0; j < c1; ++j) {
                if (grid[i][j] != grid[r0][c0]) {
                    same = false;
                    break;
                }
            }
            if (!same) {
                break;
            }
        }

        if (same) {
            return new Node(grid[r0][c0] == 1, true);
        }

        Node ret = new Node(
            true,
            false,
            dfs(grid, r0, c0, (r0 + r1) / 2, (c0 + c1) / 2),
            dfs(grid, r0, (c0 + c1) / 2, (r0 + r1) / 2, c1),
            dfs(grid, (r0 + r1) / 2, c0, r1, (c0 + c1) / 2),
            dfs(grid, (r0 + r1) / 2, (c0 + c1) / 2, r1, c1)
        );
        return ret;
    }
}

标签:Node,yyds,r0,金典,网格,grid,四叉树,c0,isLeaf
From: https://blog.51cto.com/u_15488507/7530615

相关文章

  • #yyds干货盘点#Redux 的基本使用
    1.核心概念1.什么是Redux?Redux是一个管理状态(数据)的容器,提供了可预测的状态管理2.什么是可预测的状态管理?数据在什么时候,因为什么,发生了什么改变,都是可以控制和追踪的,我们就称之为预测的状态管理3.为什么要使用Redux?React是通过数据驱动界面更新的,React负责更新界面,而我们负责......
  • #yyds干货盘点#TypeScript条件类型
    索引类型keyof会提取interface中的keyclassKeyCls{name:stringage:number}typeKeyClsExample1=keyofKeyCls//name|agefunctiongetParams(params:keyofKeyCls){}getParams('name')//正常getParams('age')//正常getParams('sex......
  • # yyds干货盘点 #盘点一个Python打包的报错问题
    大家好,我是皮皮。一、前言前几天在Python钻石群【年鱼鱼......
  • #yyds干货盘点# LeetCode程序员面试金典:2 的幂
    题目:给你一个整数 n,请你判断该整数是否是2的幂次方。如果是,返回 true ;否则,返回 false 。如果存在一个整数 x 使得 n==2x ,则认为 n 是2的幂次方。 示例1:输入:n=1输出:true解释:20=1示例2:输入:n=16输出:true解释:24=16示例3:输入:n=3输出:false示例4:输入......
  • #yyds干货盘点# LeetCode程序员面试金典:强密码检验器
    1.简述:满足以下条件的密码被认为是强密码:由至少 6 个,至多 20 个字符组成。包含至少 一个小写 字母,至少 一个大写 字母,和至少 一个数字 。不包含连续三个重复字符(比如 "Baaabb0" 是弱密码,但是 "Baaba0" 是强密码)。给你一个字符串 password ,返回 将 password......
  • #yyds干货盘点# LeetCode程序员面试金典:二叉搜索树中第K小的元素
    题目:给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从1开始计数)。 示例1:输入:root=[3,1,4,null,2],k=1输出:1示例2:输入:root=[5,3,6,2,4,null,null,1],k=3输出:3代码实现:classSolution{publicintkthSmallest(......
  • #yyds干货盘点#SQL注入之布尔注入原理
    布尔注入定义及原理:所谓盲注就是在服务器没有错误回显的时候完成注入公鸡。盲注分为布尔盲注和时间盲注布尔盲注:boolean根据注入信息返回trueorfales没有任何报错信息时间盲注:界面返回值ture无论输入任何值,返回的情况都是正常的来处。加入特定的时间函数,通过查看web页面返回......
  • #yyds干货盘点#Koa源码浅析
    Koa源码十分精简,只有不到2k行的代码,总共由4个模块文件组成,非常适合我们来学习。我们先来看段原生Node实现Server服务器的代码:consthttp=require('http');constserver=http.createServer((req,res)=>{res.writeHead(200);res.end('helloworld');});server.list......
  • # yyds干货盘点 #通过pandas读取xls文件(pd.read_excel)系统提示:no engine?
    大家好,我是皮皮。一、前言前几天在Python最强王者群【wen】问了一个Python自动化办公的问题,一起来看看吧。通过pandas读取xls文件(pd.read_excel)系统提示:noengineforfiletyppexls,请问应该如何处理呢?二、实现过程后来【隔壁......
  • #yyds干货盘点# LeetCode程序员面试金典:基本计算器 II
    题目:给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分。你可以假设给定的表达式总是有效的。所有中间结果将在 [-231,231 -1] 的范围内。注意:不允许使用任何将字符串作为数学表达式计算的内置函数,比如 eval() 。 示例1:输入:s=......