网站 图标 素材,前端微信小程序开发,seo销售话术开场白,wordpress高仿都市头条主题Hey我的编程小伙伴们#x1f44b;#xff0c;今天我要和大家分享一道我在LeetCode上遇到的超有趣的题目——编号3067的在带权树网络中统计可连接服务器对数目。这是一道非常适合练习DFS和图的题目哦#xff01;#x1f913;#x1f4bb;
邻接图是什么#xff1f;
在我们…Hey我的编程小伙伴们今天我要和大家分享一道我在LeetCode上遇到的超有趣的题目——编号3067的在带权树网络中统计可连接服务器对数目。这是一道非常适合练习DFS和图的题目哦
邻接图是什么
在我们深入题目之前先来聊聊邻接图。邻接图是一种表示图的数据结构它将每个节点的邻居节点即与该节点直接相连的节点组织在一起。简单来说邻接图就是一种方式让我们快速知道任意一个节点都和哪些节点相连。
为什么用邻接图
直观表示邻接图直观地表示了节点之间的关系让我们一眼就能看出哪些节点是直接相连的。高效查询在邻接图中查询任意两个节点之间是否存在边是非常快的。适合树结构对于树这样的无环图邻接图可以很好地表示其结构便于我们进行深度优先搜索DFS等操作。
题目解析
题目给出了一个无根带权树树上有n个节点每个节点都是一个服务器。还有一个edges数组告诉我们哪些节点之间有连接以及连接的权重。
关键的来了我们需要找出所有可以通过某个中间节点c连接的服务器对a和b。但不是随便哪个节点都能当中间人哦要满足以下条件
a b且a和b都不能是c。从c到a和从c到b的距离都能被signalSpeed整除。从c到a和从c到b的路径不能有重叠的边。
暴力枚举的可能性
题目提示中n 1000这意味着我们可以考虑使用暴力枚举的策略。因为节点的数量不是非常大所以对每个节点进行遍历和计算是可行的。
算法思路
我们构建了一个邻接图来存储每个节点的连接信息。然后通过深度优先搜索DFS遍历整棵树计算每个节点作为中间节点时能连接的服务器对的数目。
代码实现
在Scala中我们使用了ArrayBuffer来动态存储每个节点的邻居信息。DFS函数帮助我们递归地计算每个节点的贡献。最后我们只需要遍历每个节点累加它作为中间节点时能连接的服务器对数目。
import scala.collection.mutable.ArrayBufferobject Solution {def countPairsOfConnectableServers(edges: Array[Array[Int]], signalSpeed: Int): Array[Int] {val n edges.length 1val graph Array.fill(n)(ArrayBuffer[(Int, Int)]())for (e - edges) {graph(e(0)) ((e(1), e(2)))graph(e(1)) ((e(0), e(2)))}def dfs(p: Int, root: Int, curr: Int): Int {var res 0if (curr 0) {res 1}for ((v, cost) - graph(p)) {if (v ! root) {res dfs(v, p, (curr cost) % signalSpeed)}}res}val res new Array[Int](n)for (i - 0 until n) {var pre 0for ((v, cost) - graph(i)) {val cnt dfs(v, i, cost % signalSpeed)res(i) pre * cntpre cnt}}res}
}时间和空间复杂度分析
时间复杂度由于我们对每个节点都执行了DFS且每个节点的邻居都会被访问一次时间复杂度为O(N E)其中N是节点数E是边数。在这个特定问题中E接近N所以时间复杂度接近O(N^2)。空间复杂度我们使用了一个大小为N的数组来存储结果以及一个邻接图邻接图的空间复杂度取决于树的稠密程度。在最坏的情况下如果树是完全二叉树空间复杂度为O(N)。
结果
最终我们得到了一个数组count其中count[i]就是通过服务器i可连接的服务器对的数目。
#tag时间
#LeetCode挑战#算法思维#编程日常#Scala编程#树的深度优先搜索#邻接图#暴力枚举#时间空间复杂度
希望我的分享对你有所帮助如果你有更好的解法或者想法欢迎在评论区留言讨论哦我们一起进步一起加油
编程路上我们一起成长一起探索未知 以上就是今天的分享啦如果你喜欢这样的内容记得点赞和关注我哦我们下次见✨
