【深度优先搜索】【C++算法】834 树中距离之和

2024-01-26 10:52
文章标签 算法 c++ 搜索 深度 优先 834 中距离

本文主要是介绍【深度优先搜索】【C++算法】834 树中距离之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者推荐

【动态规划】【map】【C++算法】1289. 下降路径最小和 II

本文涉及知识点

深度优先搜索 树 图论

LeetCode834 树中距离之和

给定一个无向、连通的树。树中有 n 个标记为 0…n-1 的节点以及 n-1 条边 。
给定整数 n 和数组 edges ， edges[i] = [ai, bi]表示树中的节点 ai 和 bi 之间有一条边。
返回长度为 n 的数组 answer ，其中 answer[i] 是树中第 i 个节点与所有其他节点之间的距离之和。
示例 1:
输入: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
输出: [8,12,6,10,10,10]
解释: 树如图所示。
我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
也就是 1 + 1 + 2 + 2 + 2 = 8。 因此，answer[0] = 8，以此类推。
示例 2:
输入: n = 1, edges = []
输出: [0]
示例 3:
输入: n = 2, edges = [[1,0]]
输出: [1,1]
参数:
1 <= n <= 3 * 104
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
给定的输入保证为有效的树

深度优先搜索

假定节点0是树的根。
一，通过深度优先搜索计算m_vSubNodeCounts[i] ，以i为根节点的子树的节点数量。
二，通过深度优先搜索计算0到所有节点的距离。
DFSDis返回值是： cur到所有子孙节点的距离。
三，深度优先搜索，通过父节点到各点距离，计算当前节点到各点距离。
当前节点 和 当前节点的子孙节点 到 当前节点 的距离比到当前节点的父节点少1。
其它节点 到当前节点的距离比到当前节点的父节点的距离多1。

代码

核心代码

class CNeiBo2
{
public:CNeiBo2(int n, bool bDirect, int iBase = 0) :m_iN(n), m_bDirect(bDirect), m_iBase(iBase){m_vNeiB.resize(n);}CNeiBo2(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) :m_iN(n), m_bDirect(bDirect), m_iBase(iBase){m_vNeiB.resize(n);for (const auto& v : edges){m_vNeiB[v[0] - iBase].emplace_back(v[1] - iBase);if (!bDirect){m_vNeiB[v[1] - iBase].emplace_back(v[0] - iBase);}}}inline void Add(int iNode1, int iNode2){iNode1 -= m_iBase;iNode2 -= m_iBase;m_vNeiB[iNode1].emplace_back(iNode2);if (!m_bDirect){m_vNeiB[iNode2].emplace_back(iNode1);}}const int m_iN;const bool m_bDirect;const int m_iBase;vector<vector<int>> m_vNeiB;
};class Solution {
public:vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {m_vSubNodeCounts.resize(n);m_vRet.resize(n);CNeiBo2 neiBo(n, edges, false);DFSSubNodeCount(neiBo, 0, -1);m_vRet[0] = DFSDis(neiBo, 0, -1);DFS(neiBo, 0, -1);return m_vRet;}void DFS(const CNeiBo2& neiBo, int cur, int parent){if (-1 != parent){m_vRet[cur] = m_vRet[parent] - m_vSubNodeCounts[cur] + (m_vSubNodeCounts.size() - m_vSubNodeCounts[cur]);}for (const auto& next : neiBo.m_vNeiB[cur]){if (parent == next){continue;}DFS(neiBo, next, cur);}}int DFSSubNodeCount(const CNeiBo2& neiBo,int cur,int parent){int iRet = 1;for (const auto& next : neiBo.m_vNeiB[cur]){if (parent == next){continue;}iRet += DFSSubNodeCount(neiBo, next, cur);}return m_vSubNodeCounts[cur] = iRet;}int DFSDis(const CNeiBo2& neiBo, int cur, int parent)	{int iDis = m_vSubNodeCounts[cur]-1;for (const auto& next : neiBo.m_vNeiB[cur]){if (parent == next){continue;}iDis += DFSDis(neiBo, next, cur);}return iDis;}vector<int> m_vSubNodeCounts,m_vRet;
};

测试用例

template<class T>
void Assert(const T& t1, const T& 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()
{int n;vector<vector<int>> edges;{Solution sln;n = 6, edges = { {0,1},{0,2},{2,3},{2,4},{2,5} };auto res = sln.sumOfDistancesInTree(n, edges);Assert(vector<int>{8, 12, 6, 10, 10, 10}, res);}{Solution sln;n = 1, edges = {};auto res = sln.sumOfDistancesInTree(n, edges);Assert(vector<int>{0}, res);}{Solution sln;n = 2, edges = { {1,0} };auto res = sln.sumOfDistancesInTree(n, edges);Assert(vector<int>{1,1}, res);}{Solution sln;n = 3, edges = { {2,1},{0,2} };auto res = sln.sumOfDistancesInTree(n, edges);Assert(vector<int>{3,3,2}, res);}
}

2023年1月

class Solution {
public:
vector sumOfDistancesInTree(int n, vector<vector>& edges) {
m_n = n;
m_vChildDis.assign(n, -1);
m_vChildNum.resize(n, -1);
m_vNP.resize(n);
m_vTotalNum.resize(n);
for (auto& e : edges)
{
m_vNP[e[0]].push_back(e[1]);
m_vNP[e[1]].push_back(e[0]);
}
dfs1(0, -1);
dfs2(0, -1);
return m_vTotalNum;
}
void dfs1(int iCur, const int iParent)
{
int iDis = 0;
int iNum = 0;
for (const auto& next : m_vNP[iCur])
{
if (iParent == next)
{
continue;
}
dfs1(next, iCur);
iDis += m_vChildDis[next];
iNum += m_vChildNum[next];
}
m_vChildDis[iCur] = iDis + iNum;
m_vChildNum[iCur] = iNum+1;
}
void dfs2(int iCur, const int iParent)
{
if (-1 == iParent)
{
m_vTotalNum[iCur] = m_vChildDis[iCur];
}
else
{
m_vTotalNum[iCur] = m_vTotalNum[iParent] - m_vChildDis[iCur] - m_vChildNum[iCur] + (m_n - m_vChildNum[iCur]) + m_vChildDis[iCur];
}
for (const auto& next : m_vNP[iCur])
{
if (iParent == next)
{
continue;
}
dfs2(next, iCur);
}
}
vector m_vChildDis;//距离子孙节点之和
vector m_vChildNum;//子孙数量之和+1
vector m_vTotalNum;
int m_n;
vector < vector > m_vNP;
};

2023年 6月

class Solution {
public:
vector sumOfDistancesInTree(int n, vector<vector>& edges) {
m_vTotalDis.resize(n);
m_vNodeNum.resize(n);
m_vLeve.resize(n);
m_vParent.assign(n, -1);
CNeiBo2 neiBo(n, edges, false);
DSFLeveAndNodeCount(neiBo.m_vNeiB, 0, -1);
m_vTotalDis[0] = std::accumulate(m_vLeve.begin(), m_vLeve.end(), 0);
//必须按父子顺序出来
DFS(neiBo.m_vNeiB, 0, -1);
return m_vTotalDis;
}
void DFS(vector<vector>& neiBo, int iCur, int iParent)
{
if (-1 != iParent)
{
m_vTotalDis[iCur] = m_vTotalDis[m_vParent[iCur]] - m_vNodeNum[iCur] + (m_vNodeNum[0] - m_vNodeNum[iCur]);
}
for (const auto& next : neiBo[iCur])
{
if (next == iParent)
{
continue;
}
DFS(neiBo, next, iCur);
}
}
void DSFLeveAndNodeCount( vector<vector>& neiBo,int iCur,int iParent)
{
if (-1 != iParent)
{
m_vLeve[iCur] = m_vLeve[iParent] + 1;
m_vParent[iCur] = iParent;
}
m_vNodeNum[iCur] = 1;
for (const auto& next : neiBo[iCur])
{
if (next == iParent)
{
continue;
}
DSFLeveAndNodeCount(neiBo,next, iCur);
m_vNodeNum[iCur] += m_vNodeNum[next];
}
}
vector m_vTotalDis,m_vNodeNum,m_vLeve,m_vParent;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++算法】834 树中距离之和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/646565。

相关文章

深度解析Java DTO(最新推荐)

深度解析Java DTO(最新推荐)

《深度解析JavaDTO(最新推荐)》DTO（DataTransferObject）是一种用于在不同层（如Controller层、Service层）之间传输数据的对象设计模式,其核心目的是封装数据,... 目录一、什么是DTO？DTO的核心特点：二、为什么需要DTO？（对比Entity）三、实际应用场景解析
阅读更多...
深度解析Java项目中包和包之间的联系

深度解析Java项目中包和包之间的联系

《深度解析Java项目中包和包之间的联系》文章浏览阅读850次，点赞13次，收藏8次。本文详细介绍了Java分层架构中的几个关键包：DTO、Controller、Service和Mapper。_jav... 目录前言一、各大包1.DTO1.1、DTO的核心用途1.2. DTO与实体类(Entity)的区别1
阅读更多...
Java中的雪花算法Snowflake解析与实践技巧

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.
阅读更多...
从入门到精通C++11 ＜chrono＞ 库特性

从入门到精通C++11 ＜chrono＞ 库特性

《从入门到精通C++11＜chrono＞库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段（Durat
阅读更多...
C++20管道运算符的实现示例

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多，因为它实际属于c++20最为重要的
阅读更多...
Visual Studio 2022 编译C++20代码的图文步骤

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性：
阅读更多...
深度解析Python装饰器常见用法与进阶技巧

深度解析Python装饰器常见用法与进阶技巧

《深度解析Python装饰器常见用法与进阶技巧》Python装饰器（Decorator）是提升代码可读性与复用性的强大工具,本文将深入解析Python装饰器的原理,常见用法,进阶技巧与最佳实践,希望可... 目录装饰器的基本原理函数装饰器的常见用法带参数的装饰器类装饰器与方法装饰器装饰器的嵌套与组合进阶技巧
阅读更多...
c++中的set容器介绍及操作大全

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》：本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方
阅读更多...
解析C++11 static_assert及与Boost库的关联从入门到精通

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识：传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决
阅读更多...
深度解析Spring Boot拦截器Interceptor与过滤器Filter的区别与实战指南

深度解析Spring Boot拦截器Interceptor与过滤器Filter的区别与实战指南

《深度解析SpringBoot拦截器Interceptor与过滤器Filter的区别与实战指南》本文深度解析SpringBoot中拦截器与过滤器的区别,涵盖执行顺序、依赖关系、异常处理等核心差异,并... 目录Spring Boot拦截器（Interceptor）与过滤器（Filter）深度解析：区别、实现
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2