【面试经典 150 | 分治】建立四叉树

文章目录

  • 写在前面
  • Tag
  • 题目来源
  • 解题思路
    • 方法一:递归
  • 写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……

专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:

  • Tag:介绍本题牵涉到的知识点、数据结构;
  • 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
  • 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
  • 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
  • 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【四叉树】【分治】


题目来源

427. 建立四叉树


解题思路

本题参考 官方题解。

方法一:递归

思路

我们可以递归的构建出四叉树。

具体地,我们使用递归函数 dfs(r0, c0, r1, c1) 处理给定的矩阵 gridr0 行开始到 r1 - 1 行,从 c0 列开始到 c1 - 1 列的部分。 我们首先判定这一部分是否均为 0 或 1,如果是,那么这一部分对应的是一个叶节点,我们构造出对应的叶节点并结束递归;如果不是,那么这一部分对应的是一个非叶节点,我们需要将其分成四个部分:行的分界线为 r 0 + r 1 2 \frac{r0+r1}{2} 2r0+r1,列的分界线为 c 0 + c 1 2 \frac{c0+c1}{2} 2c0+c1,根据这两条分界线递归地调用 dfs 函数得到四个部分对应的树,再将它们对应地挂在非叶节点的四个子节点上。

代码

/*
// Definition for a QuadTree node.
class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;
    
    Node() {
        val = false;
        isLeaf = false;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};
*/

class Solution {
public:
    Node* construct(vector<vector<int>>& grid) {
        function<Node*(int, int, int, int)> dfs = [&](int r0, int c0, int r1, int c1) {
            for (int i = r0; i < r1; ++i) {
                for (int j = c0; j < c1; ++j) {
                    if (grid[i][j] != grid[r0][c0]) {   // 利用和网格的左上角比较是否相等判断是否是叶节点
                        return new Node(
                            true,
                            false,
                            // 对划分的四块递归计算
                            dfs(r0, c0, (r0 + r1) / 2, (c0 + c1) / 2),  // 左上
                            dfs(r0, (c0 + c1) / 2, (r0 + r1) / 2, c1),  // 右上
                            dfs((r0 + r1) / 2, c0, r1, (c0 + c1) / 2),  // 左下
                            dfs((r0 + r1) / 2, (c0 + c1) / 2, r1, c1)   // 右下
                        );
                    }
                }
            }
            // 是叶节点
            return new Node(grid[r0][c0], true);
        };
        return dfs(0, 0, grid.size(), grid.size());
    }
};

复杂度分析

时间复杂度: O ( n 2 l o g n ) O(n^2logn) O(n2logn),见 分析.

空间复杂度: O ( l o g n ) O(logn) O(logn),递归需要使用的栈空间。


写在最后

如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。

最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/597868.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C语言写的LLM训练

特斯拉前 AI 总监、OpenAI 创始团队成员 Andrej Karpathy 用 C 代码完成了 GPT-2 大模型训练过程&#xff1a;karpathy/llm.c: LLM training in simple, raw C/CUDA (github.com) 下载源码 git clone --recursive https://github.com/karpathy/llm.c.git下载模型 从HF-Mirro…

JavaScript中的RegExp和Cookie

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;JavaScript 精粹 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; 文章目录 &#x1f506;RegExp &#x1f3b2; 1 什么是正则表达式 &#x1f3b2;2 创建…

组件化开发根组件

目录 一、组件化开发介绍 二、根组件 一、组件化开发介绍 组件化&#xff1a;一个页面可以拆分成一个个组件&#xff0c;每个组件有着自己独立的结构、样式、行为。 好处&#xff1a;便于维护&#xff0c;利于复用&#xff0c;提升开发效率。 二、根组件 组件分类&#xff…

MindSponge分子动力学模拟——安装与使用

技术背景 昇思MindSpore是由华为主导的一个&#xff0c;面向全场景构建最佳昇腾匹配、支持多处理器架构的开放AI框架。MindSpore不仅仅是软件层面的工具&#xff0c;更重要的是可以协同华为自研的昇腾Ascend平台&#xff0c;做到软硬件一体的行业解决方案。基于MindSpore的高通…

Gin 框架的使用

1、Gin 快速开发 1.1、环境准备 1.1.1、导入 gin 依赖 这里就叫 gin 依赖了&#xff0c;在 Goland 命令行中输入下面的命令&#xff1a; go get -u github.com/gin-gonic/gin 1.1.2、设置代理 如果下载失败&#xff0c;最好设置一下代理&#xff0c;在 cmd 命令行中输入下…

react【实用教程】 搭建开发环境(2024版)Vite+React (官方推荐)

以项目名 reactDemo为例 1. 下载脚手架 在目标文件夹中打开命令行 npm create vite2. 安装项目依赖 cd reactDemo npm i若安装失败&#xff0c;则修改下载源重试 npm config set registry https://registry.npmmirror.com3. 启动项目 npm run dev4. 预览项目 浏览器访问 http…

亚马逊FBA头程多少钱一公斤?FBA头程怎么收费?

在亚马逊的电商生态中&#xff0c;FBA服务已经成为许多卖家提升客户满意度和销售效率的重要工具&#xff0c;然而&#xff0c;对于使用FBA服务的卖家来说&#xff0c;选择一家合适的物流合作伙伴并了解其FBA头程的收费标准和计费方式同样至关重要&#xff0c;亚马逊FBA头程多少…

Elsevier——投稿系统遇到bug时的解决方法

重要&#xff1a;找期刊客服&#xff01;&#xff01;&#xff01; 一、方法&#xff1a; 1. 点击进入与官方客服的对话 2. 按要求输入个人信息 3. 输入遇到的问题 比如&#xff1a; 主题&#xff1a;The Current Status is jammed. 详细描述&#xff1a;The Current State o…

XSS-Labs 靶场通过解析(上)

前言 XSS-Labs靶场是一个专门用于学习和练习跨站脚本攻击&#xff08;XSS&#xff09;技术的在线平台。它提供了一系列的实验场景和演示&#xff0c;帮助安全研究人员、开发人员和安全爱好者深入了解XSS攻击的原理和防御方法。 XSS-Labs靶场的主要特点和功能包括&#xff1a;…

数据结构:线性表(详解)

线性表 线性表的知识框架&#xff1a; 线性表的定义&#xff1a; 线性表是具有相同数据类型的n(n > 0)个数据元素的有限序列&#xff0c;当n 0时线性表为一个空表。 若用L命名为线性表&#xff0c;则数据集合为L {a1,a2,…,an}&#xff0c;其中a1称为表头元素&#xff0c…

【方法】如何创建RAR格式压缩文件?

为了方便存储或者传输文件&#xff0c;我们经常会把文件打包成不同格式的压缩包&#xff0c;那如果想创建的是RAR格式的压缩包&#xff0c;要如何做呢&#xff1f; RAR是WinRAR软件独有的压缩格式&#xff0c;所以我们可以通过WinRAR软件来创建RAR格式压缩包。下面分享两种创建…

02_SpringBoot程序快速启动

目录 打包命令启动启动成功测试结果 打包 点击package打包命令&#xff0c;会生成target目录&#xff0c;目录下会有生成的jar包 命令启动 打开cmd命令窗口&#xff0c;进入子项目的target目录下,输入命令后&#xff0c;回车… java -jar .\note-boot-core-1.0-SNAPSHOT.j…

一起深度学习

CIFAR-10 卷积神经网络 下载数据集构建网络运行测试 下载数据集 batchsz 32cifar_train datasets.CIFAR10(data,trainTrue,transformtorchvision.transforms.Compose([torchvision.transforms.Resize((32,32)),torchvision.transforms.ToTensor()]),downloadTrue)cifar_train …

电脑录屏什么软件好?网友力荐的3款软件!

随着电脑的使用越来越广泛&#xff0c;电脑录屏软件也成为了人们日常生活中经常需要使用到的工具。无论是录制游戏画面、教程演示还是远程教育&#xff0c;一款优秀的电脑录屏软件都能为用户提供极大的帮助&#xff0c;可是电脑录屏什么软件好呢&#xff1f;本文将为大家介绍3款…

图形存储与处理在AI去衣技术中的关键角色

引言&#xff1a; 随着人工智能技术的不断进步&#xff0c;AI去衣技术作为一种颇具争议的应用&#xff0c;已经引起了广泛的关注。该技术依托于深度学习、计算机视觉等领域的先进成果&#xff0c;通过分析图像内容实现对人物衣物的识别和去除。在这一过程中&#xff0c;图形存储…

repo跟git的关系

关于repo 大都讲的太复杂了,大多是从定义角度跟命令角度去讲解,其实从现实项目使用角度而言repo很好理解. 我们都知道git是用来管理项目的,多人开发过程中git功能很好用.现在我们知道一个项目会用一个git仓库去管理,项目的开发过程中会使用git创建分支之类的来更好的维护项目代…

stateflow绝对时间逻辑实操

使用after运算符替换at运算符 如果将at运算符与绝对时间-时间逻辑一起使用,则在尝试模拟模型时会出现错误消息。请改用after运算符。 假设您想使用(5.33,秒)的转换来定义时间延迟。 将转换更改为after(5.33秒),如图所示。这样就不报错了。 使用带有后运算符的外部自循…

【源码+文档+安装教程】校园社团信息管理系统

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了校园社团信息管理系统的开发全过程。通过分析校园社团信息管理系统管理的不足&#xff0c;创建了一个计算机管理校园社团信息管理系统的方案。文章介绍了校园社团…

【EasySpider】EasySpider+mysql执行配置异常

问题 使用易采集工具操作时候&#xff0c;遇到一个执行异常&#xff0c;后来发现没有选择数据类型 Loading stealth.min.js MySQL config file path: ./mysql_config.json 成功连接到数据库。 Successfully connected to the database. Traceback (most recent call last):…

做了两年数仓,积累的12条SQL调优技巧

本文是作者本人做数仓调优时&#xff0c;所经常使用的SQL调优技巧&#xff0c;这些“技巧”也是经过日常不断摸索、问题排查以及网络检索并且经过本人在线上大规模使用过的&#xff0c;对于下面这12条&#xff08;不算多&#xff0c;但特别有用&#xff09;调优小“技巧”&…