【深度优先搜索】【树】【C++算法】2003. 每棵子树内缺失的最小基因值

作者推荐

动态规划的时间复杂度优化

本文涉及知识点

深度优先搜索

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

有一棵根节点为 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] 互不相同。

深度优先搜索

除了基因1的节点及它的祖先，其它节点都缺少1。
DFS(cur)结束时，处理了且只处理了它哥哥及自己的后代，如果我们将基因1及其祖先调整成长子。可以将空间复杂从O(nlogn)降低到O(n)。
注意：如果不优化，空间复杂度是O(nn)，就是直接为每个节点分配空间，复制所有的后代。极端情况下，独子树的空间复杂度是O(nn)。直接用子树的空间，独子树空间复杂度O(n)；非独子树O(nlong)。

超时代码

class CParentToNeiBo
{
public:
	CParentToNeiBo(const vector<int>& parents)
	{
		m_vNeiBo.resize(parents.size());
		for (int i = 0; i < parents.size(); i++)
		{
			if (-1 == parents[i])
			{
				m_root = i;
			}
			else
			{
				m_vNeiBo[parents[i]].emplace_back(i);
			}
		}
	}
	vector<vector<int>> m_vNeiBo;
	int m_root=-1;
};

class Solution {
public:
	vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {
		CParentToNeiBo neiBo(parents);
		m_nums = nums;
		m_vIs1.resize(nums.size());
		m_ans.assign(nums.size(),1);
		m_vHas.resize(100'000+10);
		DFS1(neiBo.m_root, neiBo.m_vNeiBo);
		for (auto& v : neiBo.m_vNeiBo)
		{
			for (int j = 1; j < v.size(); j++)
			{
				if (m_vIs1[v[j]])
				{
					std::swap(v[0], v[j]);
				}
			}
		}
		DFS2(neiBo.m_root, neiBo.m_vNeiBo);
		return m_ans;
	}
	void DFS2(int cur, vector<vector<int>>& neiBo)
	{		
		for (const auto& next : neiBo[cur])
		{
			DFS2(next, neiBo);
		}
		m_vHas[m_nums[cur]] = true;
		while (m_vHas[m_iNeed])
		{
			m_iNeed++;
		}
		if (m_vIs1[cur])
		{
			m_ans[cur] = m_iNeed;
		}
	}
	bool DFS1(int cur, vector<vector<int>>& neiBo)
	{
		bool b = (1 == m_nums[cur]);		
		for (const auto& next : neiBo[cur])
		{
			b |= DFS1(next, neiBo);
		}
		return m_vIs1[cur]=b;
	}
	vector<int> m_nums,m_ans;
	vector<bool> m_vIs1;
	int m_iNeed = 1;
	vector<bool> m_vHas;
};

1及其祖先不用DFS

class CParentToNeiBo
{
public:
	CParentToNeiBo(const vector<int>& parents)
	{
		m_vNeiBo.resize(parents.size());
		for (int i = 0; i < parents.size(); i++)
		{
			if (-1 == parents[i])
			{
				m_root = i;
			}
			else
			{
				m_vNeiBo[parents[i]].emplace_back(i);
			}
		}
	}
	vector<vector<int>> m_vNeiBo;
	int m_root=-1;
};

class Solution {
public:
	vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {
		CParentToNeiBo neiBo(parents);
		m_nums = nums;
		m_vIs1.resize(nums.size());
		m_ans.assign(nums.size(),1);
		m_vHas.resize(100'000+10);
		int i1 = std::find(nums.begin(), nums.end(), 1)- nums.begin();
		while ((-1 != i1) && (nums.size() != i1))
		{
			m_vIs1[i1] = true;
			i1 = parents[i1];
		}
		for (auto& v : neiBo.m_vNeiBo)
		{
			for (int j = 1; j < v.size(); j++)
			{
				if (m_vIs1[v[j]])
				{
					std::swap(v[0], v[j]);
				}
			}
		}
		DFS2(neiBo.m_root, neiBo.m_vNeiBo);
		return m_ans;
	}
	void DFS2(int cur, vector<vector<int>>& neiBo)
	{		
		for (const auto& next : neiBo[cur])
		{
			DFS2(next, neiBo);
		}
		m_vHas[m_nums[cur]] = true;		
		if (m_vIs1[cur])
		{
            while (m_vHas[m_iNeed])
		{
			m_iNeed++;
		}
			m_ans[cur] = m_iNeed;
		}
	}
	vector<int> m_nums,m_ans;
	vector<bool> m_vIs1;
	int m_iNeed = 1;
	vector<bool> m_vHas;
};

测试用例


template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	vector<int> parents,  nums;
	{
		Solution sln;
		parents = { -1, 0, 0, 2 }, nums = { 1, 2, 3, 4 };
		auto res = sln.smallestMissingValueSubtree(parents, nums);
		Assert({ 5,1,1,1 }, res);
	}
	
	{
		Solution sln;
		parents = { -1, 0, 1, 0, 3, 3 }, nums = { 5, 4, 6, 2, 1, 3 };
		auto res = sln.smallestMissingValueSubtree(parents, nums);
		Assert({ 7,1,1,4,2,1 }, res);
	}

	{
		Solution sln;
		parents = { -1, 2, 3, 0, 2, 4, 1 }, nums = { 2, 3, 4, 5, 6, 7, 8 };
		auto res = sln.smallestMissingValueSubtree(parents, nums);
		Assert({ 1,1,1,1,1,1,1 }, res);
	}
}

2023年2月版（当时能过）

class Solution {
public:
vector smallestMissingValueSubtree(const vector& parents, const vector& nums) {
m_c = nums.size();
m_vDirect.resize(m_c);
for (int i = 1; i < parents.size(); i++)
{
m_vDirect[parents[i]].push_back(i);
}
m_vVisiteValue.resize(m_c + 1);
m_vRet.assign(m_c, 1);
for (int i = 0; i < nums.size(); i++)
{
if (1 == nums[i])
{
DFS(i, -1,parents, nums);
break;
}
}
return m_vRet;
}
void DFS(int iCur, int iFromChild,const vector& parents, const vector& nums)
{
if (-1 == iCur)
{
return;
}
DFSForValue(iCur, iFromChild, nums);
int iMiss = (-1 == iFromChild) ? 1 : m_vRet[iFromChild];
while ((iMiss < m_vVisiteValue.size()) && (m_vVisiteValue[iMiss]))
{
iMiss++;
}
m_vRet[iCur] = iMiss;
DFS(parents[iCur], iCur, parents, nums);
}
void DFSForValue(int iCur, int iFromChild, const vector& nums)
{
m_vVisiteValue[nums[iCur]] = true;
for (auto& next : m_vDirect[iCur])
{
if (next == iFromChild)
{
continue;
}
DFSForValue(next, iFromChild, nums);
}
}
int m_c;
vector<vector> m_vDirect;
vector m_vRet;
vector m_vVisiteValue;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

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

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

相关文章

AXI4的网格设计Block Design

AXI4的网格设计Block Design

一、引出时钟和时钟复位 然后同样的把主接口和从接口的两个时钟和两个reset信号连接在一起。 二、分配地址 三、验证设计 点击图中的Validate Design验证设计&#xff0c;如果不对的话会有报错 报错如下 四、Generate Output Product和Creat HDL Wrapper 4.1 Generate Output…
阅读更多...
设计模式之策略模式详解

设计模式之策略模式详解

目录 什么是策略模式 应用场景 业务场景实现 抽象类 实现类 Context上下文 测试类 策略模式的优缺点 什么是策略模式 他将定义的算法家族、分别封装起来&#xff0c;让他们之间可以相互替换&#xff0c;从而让算法的变化不会影响到使用算法的用户。 策略模式使用的就是…
阅读更多...
【IO流系列】字符流练习（拷贝、文件加密、修改文件数据）

【IO流系列】字符流练习（拷贝、文件加密、修改文件数据）

字符流练习 练习1&#xff1a;文件夹拷贝1.1 需求1.2 代码实现1.3 输出结果 练习2&#xff1a;文件加密与解密2.1 需求2.2 代码实现2.3 输出结果 练习3&#xff1a;修改文件数据&#xff08;常规方法&#xff09;3.1 需求3.2 代码实现3.3 输出结果 练习4&#xff1a;修改文件数…
阅读更多...
最小高度树-力扣（Leetcode）

最小高度树-力扣（Leetcode）

题目链接 最小高度树 思路&#xff1a;本质上是找到树中的最长路径。当最长路径上中间点&#xff08;若路经长为偶数&#xff0c;则中间点仅有一个&#xff0c;否者中间点有两个&#xff09;作为根时&#xff0c;此时树高最小。 Code: class Solution { public://拓扑排序int…
阅读更多...
武汉灰京文化：多样化推广与创新引领游戏行业

武汉灰京文化：多样化推广与创新引领游戏行业

作为专业的游戏推广服务商&#xff0c;武汉灰京文化注重多样化的推广策略&#xff0c;通过与各大媒体、社交平台和游戏社区建立紧密的合作关系&#xff0c;为游戏企业提供全方位的推广服务。他们通过精确的广告投放、内容创作和社交媒体互动等方式&#xff0c;将游戏信息传播给…
阅读更多...
Unity曲柄滑块四杆机构运动计算

Unity曲柄滑块四杆机构运动计算

一、运动效果 二、机构的介绍 曲柄长度&#xff1a;a&#xff0c;线段AB长度 连杆长度&#xff1a;b&#xff0c;线段BC长度 偏心距离&#xff1a;e&#xff0c;滑块轨迹与曲柄中心点A的垂直距离 三、已知点A点B和e的值&#xff0c;计算C点的位置 1、计算s的值 var h math.…
阅读更多...
阻塞队列介绍

阻塞队列介绍

阻塞队列 kafka是目前来说性能最好的消息队列服务器&#xff0c;能处理TB级别的数据 作用:点赞、评论时&#xff0c;服务器会自动给某个用户发送通知 kafka是个框架&#xff0c;如果不用框架还要解决类似问题&#xff0c;就要用到阻塞队列 BlockingQueue 阻塞队列就是一个…
阅读更多...
【C++】vector 的常用接口

【C++】vector 的常用接口

目录 一、vector是什么❓ 二、vector的使用 1、构造函数 2、修改数据 ⭕️size ⭕️capacity ⭕️empty ⭕️clear ⭕️resize&#xff08;重要&#xff09; ⭕️reserve&#xff08;重要&#xff09; ​3、遍历数据 ⭕️operator[ ] &#xff08;重要&#xff09; …
阅读更多...
35 Spring整合Elasticsearch

35 Spring整合Elasticsearch

文章目录 Spring整合Elasticsearch引入依赖配置Elasticsearch解决冲突 使用ElasticsearchSpring Data Elasticsearch建立映射关系常用方法添加数据修改数据删除数据搜索数据&#xff08;es核心&#xff09;步骤构造搜索条件 并 应用进行查询使用查询结果 Spring整合Elasticsear…
阅读更多...
wps没保存关闭了怎么恢复数据？恢复文件教程

wps没保存关闭了怎么恢复数据？恢复文件教程

Microsoft Word是我们不可或缺的工具。很多小伙伴都遇到在WPS中编辑文件时&#xff0c;它可能会突然闪退&#xff0c;或者忘记及时保存文件就直接关闭了&#xff0c;导致我们辛苦编辑的文档丢失。面对这种情况我们该如何应对&#xff0c;尽量减小损失呢&#xff1f;接下来让我为…
阅读更多...
is_sorted()函数的练习

is_sorted()函数的练习

仅是用来巩固训练verctor容器与is_sorted()、next_permutation()函数 #include <bits/stdc.h> using namespace std;bool cmp1(int a,int b){if(a>b)return true;return false; } bool cmp2(int a,int b){if(a<b)return true;return false; } int main(){vector<…
阅读更多...
博客笔记项目的自动化测试

博客笔记项目的自动化测试

作者简介&#xff1a;大家好&#xff0c;我是未央&#xff1b; 博客首页&#xff1a;未央.303 系列专栏&#xff1a;测试开发项目 每日一句&#xff1a;人的一生&#xff0c;可以有所作为的时机只有一次&#xff0c;那就是现在&#xff01;&#xff01;&#xff01;! 文章目录 …
阅读更多...
Mongodb基础(node.js版)

Mongodb基础(node.js版)

一、Mongodb 介绍 Mongodb 是一个文档数据库&#xff0c;以文档形式存储数据&#xff0c;格式类似于 JSON 与 Mysql 的特点及选型对照 MongodbMysql关系类型非关系型关系型存储类型文档存储&#xff08;类似于写 Word &#xff09;表格存储 &#xff08;类似于写 Excle&…
阅读更多...
浙江大学主办！2024年第7届信息通信与信号处理国际会议（ ICICSP2024）征稿开启！

浙江大学主办！2024年第7届信息通信与信号处理国际会议（ ICICSP2024）征稿开启！

会议官网 IEEE | ICICSP 2024 学术会议查询-学术会议交流服务平台-爱科会易 (uconf.com)​www.uconf.com/
阅读更多...
Day12：信息打点-Web应用源码泄漏开源闭源指纹识别GITSVNDS备份

Day12：信息打点-Web应用源码泄漏开源闭源指纹识别GITSVNDS备份

目录 开源-CMS指纹识别源码获取方式 闭源-习惯&配置&特性等获取方式 闭源-托管资产平台资源搜索监控 思维导图 章节点 Web&#xff1a;语言/CMS/中间件/数据库/系统/WAF等 系统&#xff1a;操作系统/端口服务/网络环境/防火墙等 应用&#xff1a;APP对象/API接口/微…
阅读更多...
17.来自Sora的夺舍妄想——享元模式详解

17.来自Sora的夺舍妄想——享元模式详解

OpenAI 的 Sora 模型面世之后&#xff0c;可以说人类抵御AI的最后阵地也沦陷了。 在此之前&#xff0c;人们面对AI交互式对话&#xff0c;AI制图&#xff0c;AI建模之类的奇迹时&#xff0c;还可以略微放肆的说&#xff1a;“的确很神奇&#xff0c;这毕竟还是比人类世界低了一…
阅读更多...
【go从入门到精通】go包，内置类型和初始化顺序

【go从入门到精通】go包，内置类型和初始化顺序

大家好&#xff0c;这是我给大家准备的新的一期专栏&#xff0c;专门讲golang&#xff0c;从入门到精通各种框架和中间件&#xff0c;工具类库&#xff0c;希望对go有兴趣的同学可以订阅此专栏。 go基础 。 Go文件名&#xff1a; 所有的go源码都是以 ".go" 结尾&…
阅读更多...
pytorch -- torch.nn网络结构

pytorch -- torch.nn网络结构

1. 官网描述 官网 使用 torch.nn 模块&#xff0c;我们可以创建自定义的神经网络模型&#xff0c;并使用 PyTorch 提供的优化器&#xff08;如 torch.optim&#xff09;和损失函数来训练和优化模型。 2. 常见结构 1.卷积操作 定义&#xff1a; 二维卷积 1.1版本 nn.functio…
阅读更多...
香港大学发布思维扩散DoT，让思维在时间上扩散，提效保质！

香港大学发布思维扩散DoT，让思维在时间上扩散，提效保质！

引言&#xff1a;探索结合扩散模型与思维链来提升大模型推理能力 在人工智能领域&#xff0c;大语言模型&#xff08;LLMs&#xff09;已经引起了广泛的关注&#xff0c;它们在自然语言处理和机器学习的经典问题上展现出了显著的推理能力。特别是&#xff0c;思维链&#xff0…
阅读更多...
Vue开发实例（九）动态路由实现左侧菜单导航

Vue开发实例（九）动态路由实现左侧菜单导航

之前在【Vue开发实例&#xff08;六&#xff09;实现左侧菜单导航】文中实现了菜单的导航&#xff0c;本篇是在那个基础上改造的。 动态路由实现左侧菜单导航 一、动态菜单创建二、根据菜单数据来创建路由三、添加路由已加载标记&#xff0c;省的每次点击菜单都要加载 一、动态…
阅读更多...
最新文章

Copyright @ 2022~2023