LeetCode:2003. 每棵子树内缺失的最小基因值(C++)

目录

2003. 每棵子树内缺失的最小基因值

题目描述:

实现代码与解析:

dfs + 启发式合并

原理思路:


2003. 每棵子树内缺失的最小基因值

题目描述:

        有一棵根节点为 0 的 家族树 ,总共包含 n 个节点,节点编号为 0 到 n - 1 。给你一个下标从 0 开始的整数数组 parents ,其中 parents[i] 是节点 i 的父节点。由于节点 0 是  ,所以 parents[0] == -1 。

总共有 105 个基因值,每个基因值都用 闭区间 [1, 105] 中的一个整数表示。给你一个下标从 0 开始的整数数组 nums ,其中 nums[i] 是节点 i 的基因值,且基因值 互不相同 。

请你返回一个数组 ans ,长度为 n ,其中 ans[i] 是以节点 i 为根的子树内 缺失 的 最小 基因值。

节点 x 为根的 子树 包含节点 x 和它所有的 后代 节点。

示例 1:

输入:parents = [-1,0,0,2], nums = [1,2,3,4]
输出:[5,1,1,1]
解释:每个子树答案计算结果如下:
- 0:子树包含节点 [0,1,2,3] ,基因值分别为 [1,2,3,4] 。5 是缺失的最小基因值。
- 1:子树只包含节点 1 ,基因值为 2 。1 是缺失的最小基因值。
- 2:子树包含节点 [2,3] ,基因值分别为 [3,4] 。1 是缺失的最小基因值。
- 3:子树只包含节点 3 ,基因值为 4 。1是缺失的最小基因值。

示例 2:

输入:parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]
输出:[7,1,1,4,2,1]
解释:每个子树答案计算结果如下:
- 0:子树内包含节点 [0,1,2,3,4,5] ,基因值分别为 [5,4,6,2,1,3] 。7 是缺失的最小基因值。
- 1:子树内包含节点 [1,2] ,基因值分别为 [4,6] 。 1 是缺失的最小基因值。
- 2:子树内只包含节点 2 ,基因值为 6 。1 是缺失的最小基因值。
- 3:子树内包含节点 [3,4,5] ,基因值分别为 [2,1,3] 。4 是缺失的最小基因值。
- 4:子树内只包含节点 4 ,基因值为 1 。2 是缺失的最小基因值。
- 5:子树内只包含节点 5 ,基因值为 3 。1 是缺失的最小基因值。

示例 3:

输入:parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]
输出:[1,1,1,1,1,1,1]
解释:所有子树都缺失基因值 1 。

提示:

  • n == parents.length == nums.length
  • 2 <= n <= 105
  • 对于 i != 0 ,满足 0 <= parents[i] <= n - 1
  • parents[0] == -1
  • parents 表示一棵合法的树。
  • 1 <= nums[i] <= 105
  • nums[i] 互不相同。

实现代码与解析:

dfs + 启发式合并

class Solution {
public:// 邻接表vector<int> h = vector<int>(1e5 + 10, -1); vector<int> e = vector<int>(1e5 + 10, 0); vector<int> ne = vector<int>(1e5 + 10, 0);int idx = 0;void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;}vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {int n = parents.size();// 存图 加边 邻接表for (int i = 1; i < n; i++) { // 这里从1开始,找半天错。。add(parents[i], i);}vector<int> res(n, 1); // 结果数组vector<unordered_set<int>> gene(n); // 包含此节点 与 其子树 的基因合集setfunction<int(int)> dfs = [&](int cur) -> int{gene[cur].insert(nums[cur]); // 当前节点基因值放入for (int i = h[cur]; ~i; i = ne[i]) {int j = e[i]; // 子节点res[cur] = max(res[cur], dfs(j)); // 此节点为根缺失的最小的基因,一定比子树缺失的最小基因大或等于,所以这里取个max// 向上传递合集,小的合并到大的效率快,所以先判断(选择是否先交换),在树中属于中序处理if (gene[cur].size() < gene[j].size()) {gene[cur].swap(gene[j]);}gene[cur].merge(gene[j]); // 合并}// 根据res寻找此节点的结果, 一定比子树大或等于,++遍历即可,找到第一个没有的最小基因while (gene[cur].count(res[cur]) > 0) {res[cur]++;}return res[cur];};dfs(0); // dfsreturn res;}
};

原理思路:

        vector<unordered_set<int>> gene(n); // 包含此节点 与 其子树 的基因合集set

        dfs返回此节点的结果(缺失基因最小值),递归向上处理,每次将子树的集合与其根节点集合合并,根节点的缺失最小值一定大于等于其子树。从最大子树缺失的最小基因开始++遍历,找到第一个不在集合中的值,就为以此节点为根的树的缺失的最小基因。

        此题的核心,就是我们不仅要向上传递子树缺失的最小基因,还要根据树中包含的节点来找出缺失基因,所以每个节点多了set来记录以它为根的树包含的节点,每次向上来合并set是此题的关键。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Linux】虚拟机部署与发布J2EE项目(Linux版本)

&#x1f389;&#x1f389;欢迎来到我的CSDN主页&#xff01;&#x1f389;&#x1f389; &#x1f3c5;我是Java方文山&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; &#x1f31f;推荐给大家我的专栏《微信小程序开发实战》。&#x1f3af;&#x1f3a…

【Vue3-Flask-BS架构Web应用】实践笔记1-使用一个bat脚本自动化完整部署环境

前言 近年来&#xff0c;Web开发已经成为计算机科学领域中最热门和多产的领域之一。Python和Vue.js是两个备受欢迎的工具&#xff0c;用于构建现代Web应用程序。在本教程中&#xff0c;我们将探索如何使用这两个工具来创建一个完整的Web项目。我们将完成从安装Python和Vue.js到…

从0到1之微信小程序快速入门(02)

目录 页面导航 - 声明式导航 1. 导航到 tabBar 页面 2. 导航到非 tabBar 页面 3. 后退导航 ​编辑 页面导航 - 编程式导航 页面导航 - 导航传参 页面事件 - 下拉刷新事件 监听下拉刷新事件 停止下拉刷新的效果 页面事件 - 上拉触底事件 监听页面的上拉触底事件 配置…

项目部署之OpenResty

项目部署之OpenResty 1. OpenResty介绍 OpenResty 是一个基于Nginx的高性能Web平台&#xff0c;用于方便地搭建能够处理超高并发、扩展性极高的动态Web应用、Web服务和动态网关。具备下列特点&#xff1a; 具备Nginx的完整功能基于Lua语言进行扩展&#xff0c;集成了大量精良…

cmake多目录构建初步成功

目录和代码和 首次cmake 多目录构建失败 此文一样&#xff1b; 只有一个CMakeLists.txt&#xff1b; cmake_minimum_required(VERSION 3.10) project(mytest3 VERSION 1.0) include_directories("${PROJECT_SOURCE_DIR}/include") add_executable(mytest3 src/main…

vue2:路由前置守卫无法获取到this.$store.state.xxx

在获取到vuex的数据时候&#xff0c;想在router目录下的index.js文件去获取到vuex仓库中声明的全局变量&#xff0c;但是通过this.$store.stote.xxx去获取的时候&#xff0c;报错提示&#xff1a;$store未定义 一、store/index.js const store new Vuex.Store({state: {// 属…

WPS中图的自动编号及引用

WPS中图的自动编号及引用 图的自动编号图编号的引用图编号及引用的更新 图的自动编号 将光标放置在需要插入编号的位置点击“引用”→“题注”&#xff1a; 点击“引用”→“题注”&#xff1a; 点击“编号”&#xff0c;设置图的编号格式&#xff0c;可勾选“包含章节编号”&…

铁轨(Rails, ACM/ICPC CERC 1997, UVa 514)rust解法

有一个火车站&#xff0c;铁轨铺设如图6-1所示。有n节车厢从A方向驶入车站&#xff0c;按进站顺序编号为1&#xff5e;n。你的任务是判断是否能让它们按照某种特定的顺序进入B方向的铁轨并驶出车站。例如&#xff0c;出栈顺序(5 4 1 2 3)是不可能的&#xff0c;但(5 4 3 2 1)是…

【错误解决方案】ModuleNotFoundError: No module named ‘xgboost‘

1. 错误提示 在尝试导入名为xgboost的模块时出现了ModuleNotFoundError。 错误提示&#xff1a;ModuleNotFoundError: No module named xgboost 这个错误通常意味着Python环境中没有安装你试图导入的模块。 2. 解决方案 安装xgboost模块即可解决上述问题。 可以通过Python…

对音频文件的处理:音频信息,读取内容,获取时长,切割音频,pcm与wav互转

音频处理发现的比较简单的代码&#xff0c;原作者代码在github&#xff1a;GitHub - silencesmile/python_wav: 对音频文件的处理&#xff1a;音频信息&#xff0c;读取内容&#xff0c;获取时长&#xff0c;切割音频&#xff0c;pcm与wav互转 可以按给定的开始和结束时间调用代…

软件安利——火绒安全

近年来&#xff0c;以优化、驱动、管理为目标所打造的软件屡见不鲜&#xff0c;大同小异的电脑管家相继走入了公众的视野。然而&#xff0c;在这日益急功近利的社会氛围驱动之下&#xff0c;真正坚持初心、优先考虑用户体验的电脑管家逐渐湮没在了浪潮之中。无论是鲁大师&#…

Dockerfile文件自动化生成R4L镜像

Dockerfile文件自动化生成R4L镜像的步骤 1、安装Docker&#xff1a;2、使用Dockerfile一键生成镜像&#xff1a;3、查看生成的Docker镜像&#xff1a;4、删除Docker镜像&#xff1a;5、生成Docker容器&#xff1a;6、查看容器7、删除容器 1、安装Docker&#xff1a; curl -fsS…

YOLOv5/YOLOv7改进: AIFI (尺度内特征交互)助力YOLO | YOLO终结者?RT-DETR一探究竟

💡💡💡本文全网首发独家改进: AIFI (尺度内特征交互)助力YOLO ,提升尺度内和尺度间特征交互能力,同时降低多个尺度的特征之间进行注意力运算,计算消耗较大等问题 推荐指数:五星 AIFI | 亲测在多个数据集能够实现涨点 💡💡💡Yolov5/Yolov7魔术师,独家首…

Py之optimum:optimum的简介、安装、使用方法之详细攻略

Py之optimum&#xff1a;optimum的简介、安装、使用方法之详细攻略 目录 optimum的简介 1、加速推理 Optimum 提供多种工具&#xff0c;用于在不同生态系统上导出和运行优化模型&#xff1a; 2、功能概述 optimum的安装 1、如果您想使用 Optimum 的加速器特定功能&#…

IOI车机系统刷机和改包笔记2 - 改包脚本

前言&#xff1a; 最近对雪佛兰改包需求感兴趣的网友很多&#xff0c;大家都遇上了很多奇怪的问题&#xff0c;这里就我自己使用的环境和脚本进行分享&#xff0c;供大家参考。 1. 准备环境 我这里使用Ubuntu系统进行操作 andyandy-vm:~$ sudo lsb_release -a No LSB module…

2023年CCF中国开源大会“大模型时代的智能化软件工程新范式”分论坛成功举行...

2023年CCF中国开源大会“大模型时代的智能化软件工程新范式”分论坛于10月21日在湖南长沙成功举行。本次论坛聚焦大模型时代的智能化软件新生态以及相应的软件工程新范式&#xff0c;邀请了多位来自学术界和工业界的专家进行分享和交流&#xff0c;共设置了5个主题报告和1个Pan…

设计师看后惊叹:当泥色走进室内空间的时候竟有此番效果

在美国的洛杉矶&#xff0c;一座引人注目的度假别墅彰显了自己的独特魅力。建筑师 Ron Radziner 说&#xff1a;“这是一座现代住宅&#xff0c;采用风化木、深色灰泥和绿色屋顶等与峡谷环境相关的材料&#xff0c;设计得通透、开放。” Zwickl 解释说&#xff1a;"他们想…

Git 入门指南:从新手到高手的完全指南

Git是一种强大的分布式版本控制系统&#xff0c;广泛应用于软件开发中。它的使用不仅可以帮助开发团队更好地管理代码&#xff0c;还可以提高团队协作效率和代码质量。随着软件开发的不断发展&#xff0c;版本控制成为了程序员必备的一项技能。 Git的基本概念 Git的基本概念对…

基因家族扩张与收缩分析-CAFE5

CAFE(Computational Analysis of gene Family Evolution)是一款以解释系统发育历史的方式分析基因家族大小变化的软件&#xff0c;这种分析常被称为基因家族收缩扩张(Gene family expansions and contractions)分析。 CAFE使用出生和死亡过程来模拟用户指定的系统发育树中的基…

在centos服务器中完成jdk,tomcat,MySQL的安装以及前后端分离项目中后端的部署

目录 一. jdk&#xff0c;tomcat的安装 1.将要安装的软件压缩包放入到centos服务器上 2. 解压对应的安装包 3. jdk环境变量配置 4. tomcat启动 5. 关闭防火墙 二. MySQL安装 1. 卸载mariadb&#xff0c;否则安装MySql会出现冲突(先查看后删除再查看) 2. 将MySQL安装包解…