怎么利用网站做产品推广,适合女生的计算机专业有哪些,建网站需多少钱,培训网站平台怎样做133. 克隆图 题目-中等难度示例1. bfs 题目-中等难度
给你无向 连通 图中一个节点的引用#xff0c;请你返回该图的 深拷贝#xff08;克隆#xff09;。
图中的每个节点都包含它的值 val#xff08;int#xff09; 和其邻居的列表#xff08;list[Node]#xff09;。… 133. 克隆图 题目-中等难度示例1. bfs 题目-中等难度
给你无向 连通 图中一个节点的引用请你返回该图的 深拷贝克隆。
图中的每个节点都包含它的值 valint 和其邻居的列表list[Node]。
class Node { public int val; public List neighbors; }
测试用例格式
简单起见每个节点的值都和它的索引相同。例如第一个节点值为 1val 1第二个节点值为 2val 2以此类推。该图在测试用例中使用邻接列表表示。
邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。
给定节点将始终是图中的第一个节点值为 1。你必须将 给定节点的拷贝 作为对克隆图的引用返回。
示例
示例 1 输入adjList [[2,4],[1,3],[2,4],[1,3]] 输出[[2,4],[1,3],[2,4],[1,3]] 解释 图中有 4 个节点。 节点 1 的值是 1它有两个邻居节点 2 和 4 。 节点 2 的值是 2它有两个邻居节点 1 和 3 。 节点 3 的值是 3它有两个邻居节点 2 和 4 。 节点 4 的值是 4它有两个邻居节点 1 和 3 。 示例 2 输入adjList [[]] 输出[[]] 解释输入包含一个空列表。该图仅仅只有一个值为 1 的节点它没有任何邻居。 示例 3 输入adjList [] 输出[] 解释这个图是空的它不含任何节点。 示例 4 输入adjList [[2],[1]] 输出[[2],[1]] 提示 节点数不超过 100 。每个节点值 Node.val 都是唯一的1 Node.val 100。无向图是一个简单图这意味着图中没有重复的边也没有自环。由于图是无向的如果节点 p 是节点 q 的邻居那么节点 q 也必须是节点 p 的邻居。图是连通图你可以从给定节点访问到所有节点。 来源力扣LeetCode 链接https://leetcode.cn/problems/summary-ranges 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
1. bfs
时间 48ms 击败 74.56%使用 Python3 的用户 内存 15.95MB 击败 90.86%使用 Python3 的用户 # Definition for a Node.
class Node:def __init__(self, val 0, neighbors None):self.val valself.neighbors neighbors if neighbors is not None else []
class Solution:def cloneGraph(self, node: Optional[Node]) - Optional[Node]:# 如果没有节点存在, 直接返回空节点if not node:return node# 创建字典visited defaultdict()# 根节点放入列表中li [node]# 将放入的根节点添加到字典, 以对象的形式存在visited[node] Node(node.val,[])# 广度遍历while li:# 获取节点a li.pop(0)# 遍历当前节点的neighborsfor n in a.neighbors:# 如果 neighbor中的节点不在字典中if n not in visited:# 添加节点作为对象到字典visited[n] Node(n.val,[])# 添加节点到lili.append(n)# 当前对象的neighbors列表中添加关联对象visited[a].neighbors.append(visited[n])# 返回node对象return visited[node]
