备案控制台
开发者社区 开发与运维 文章 正文

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

2024-04-10 19
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【深度优先搜索】【树】【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++**实现。

文章标签：
算法
C++
测试技术
机器学习/深度学习
C#
关键词：
C++算法
树c++算法
深度优先搜索C++
C++深度优先搜索
树C++
闻缺陷则喜何志丹
目录
相关文章
拓端数据部落
|
2天前
|
机器学习/深度学习 数据采集 算法
Python用逻辑回归、决策树、SVM、XGBoost 算法机器学习预测用户信贷行为数据分析报告
Python用逻辑回归、决策树、SVM、XGBoost 算法机器学习预测用户信贷行为数据分析报告
拓端数据部落
29 1
懒懒学c
|
2天前
|
存储 C++ 容器
c++的学习之路：26、AVL树
c++的学习之路：26、AVL树
懒懒学c
29 0
1941623231718325
|
2天前
|
机器学习/深度学习 算法
理解并应用机器学习算法：决策树
【5月更文挑战第12天】决策树是直观的分类与回归机器学习算法，通过树状结构模拟决策过程。每个内部节点代表特征属性，分支代表属性取值，叶子节点代表类别。构建过程包括特征选择（如信息增益、基尼指数等）、决策树生成和剪枝（预剪枝和后剪枝）以防止过拟合。广泛应用在信贷风险评估、医疗诊断等领域。理解并掌握决策树有助于解决实际问题。
1941623231718325
25 6
盒马盒马
|
2天前
|
存储 算法 C++
数据结构/C++：AVL树
数据结构/C++：AVL树
盒马盒马
10 2
Bigcrab__
|
2天前
|
存储 缓存 算法
数据结构与算法 树（B树，B+树，红黑树待完善）
数据结构与算法 树（B树，B+树，红黑树待完善）
Bigcrab__
15 0
Yawesh
|
2天前
|
存储 机器学习/深度学习 算法
【C++入门到精通】C++入门 —— AVL 树（自平衡二叉搜索树）
【C++入门到精通】C++入门 —— AVL 树（自平衡二叉搜索树）
Yawesh
11 2
拓端数据部落
|
2天前
|
机器学习/深度学习 算法 数据可视化
Matlab决策树、模糊C-均值聚类算法分析高校教师职称学历评分可视化
Matlab决策树、模糊C-均值聚类算法分析高校教师职称学历评分可视化
拓端数据部落
11 0
桃李春风一杯酒
|
2天前
|
机器学习/深度学习 算法 数据可视化
【Python机器学习专栏】决策树算法的实现与解释
【4月更文挑战第30天】本文探讨了决策树算法，一种流行的监督学习方法，用于分类和回归。文章阐述了决策树的基本原理，其中内部节点代表特征判断，分支表示判断结果，叶节点代表类别。信息增益等标准用于衡量特征重要性。通过Python的scikit-learn库展示了构建鸢尾花数据集分类器的示例，包括训练、预测、评估和可视化决策树。最后，讨论了模型解释和特征重要性评估在优化中的作用。
桃李春风一杯酒
9 1
拓端数据部落
|
2天前
|
机器学习/深度学习 算法 搜索推荐
R语言LASSO特征选择、决策树CART算法和CHAID算法电商网站购物行为预测分析
R语言LASSO特征选择、决策树CART算法和CHAID算法电商网站购物行为预测分析
拓端数据部落
18 0
拓端数据部落
|
2天前
|
机器学习/深度学习 数据采集 算法
共享单车需求量数据用CART决策树、随机森林以及XGBOOST算法登记分类及影响因素分析
共享单车需求量数据用CART决策树、随机森林以及XGBOOST算法登记分类及影响因素分析
拓端数据部落
23 0

热门文章

最新文章

  • 1
    最佳实践｜如何使用c++开发redis module
  • 2
    基础算法学习笔记（C++）
  • 3
    C++的STL学习笔记
  • 4
    【重学C++】【内存】关于C++内存分区，你可能忽视的那些细节
  • 5
    C++中的科学计数法
  • 6
    Qt：强大的跨平台C++应用程序开发框架
  • 7
    c++中常用库函数
  • 8
    探索c++：string常用接口 迷雾
  • 9
    【C++成长记】C++入门 |函数重载、引用、内联函数
  • 10
    Sublime Text 3配置C/C++开发环境
  • 1
    视觉智能平台常见问题之其他算法定制化开发如何解决
    80
  • 2
    使用Python实现图像处理中的边缘检测算法
    99
  • 3
    利用机器学习算法改善电商推荐系统的效率
    95
  • 4
    Python基础算法解析：K最近邻算法
    38
  • 5
    【数据结构与算法】—— 手撕红黑树
    44
  • 6
    【优选算法】—— 字符串匹配算法
    51
  • 7
    【优选算法】—— 滑动窗口类问题
    46
  • 8
    【算法】——全排列算法讲解
    40
  • 9
    【排序算法】数据结构排序详解
    51
  • 10
    数据结构——排序算法之快速排序
    36

    • 相关课程

    更多
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • C++ 入门教程开发文档
  • 神经网络概览及算法详解
  • 【算法实战】10. 树回归算法

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • TLS1.3的后量子算法集成
  • RSA非对称加密算法
  • 欧拉图的构造性证明与算法实现
    • 下一篇
    2024年阿里云免费云服务器及学生云服务器申请教程参考