【LeetCode】133.CloneGraph克隆图（Medium）（JAVA）

【LeetCode】133. Clone Graph 克隆图&＃xff08;Medium&＃xff09;&＃xff08;JAVA&＃xff09;

题目地址: https://leetcode.com/problems/clone-graph/

题目描述&＃xff1a;

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

class Node {public int val;public List neighbors;
}


Test case format:

For simplicity sake, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val &＃61; 1, the second node with val &＃61; 2, and so on. The graph is represented in the test case using an adjacency list.

Adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val &＃61; 1. You must return the copy of the given node as a reference to the cloned graph.

Example 1:

Input: adjList &＃61; [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val &＃61; 1)&＃39;s neighbors are 2nd node (val &＃61; 2) and 4th node (val &＃61; 4).
2nd node (val &＃61; 2)&＃39;s neighbors are 1st node (val &＃61; 1) and 3rd node (val &＃61; 3).
3rd node (val &＃61; 3)&＃39;s neighbors are 2nd node (val &＃61; 2) and 4th node (val &＃61; 4).
4th node (val &＃61; 4)&＃39;s neighbors are 1st node (val &＃61; 1) and 3rd node (val &＃61; 3).


Example 2:

Input: adjList &＃61; [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val &＃61; 1 and it does not have any neighbors.


Example 3:

Input: adjList &＃61; []
Output: []
Explanation: This an empty graph, it does not have any nodes.


Example 4:

Input: adjList &＃61; [[2],[1]]
Output: [[2],[1]]


Constraints:

• 1 <&＃61; Node.val <&＃61; 100
• Node.val is unique for each node.
• Number of Nodes will not exceed 100.
• There is no repeated edges and no self-loops in the graph.
• The Graph is connected and all nodes can be visited starting from the given node.

题目大意

给你无向 连通 图中一个节点的引用&＃xff0c;请你返回该图的 深拷贝&＃xff08;克隆&＃xff09;。

图中的每个节点都包含它的值 val&＃xff08;int&＃xff09; 和其邻居的列表&＃xff08;list[Node]&＃xff09;。

class Node {public int val;public List neighbors;
}


测试用例格式&＃xff1a;

简单起见&＃xff0c;每个节点的值都和它的索引相同。例如&＃xff0c;第一个节点值为 1&＃xff08;val &＃61; 1&＃xff09;&＃xff0c;第二个节点值为 2&＃xff08;val &＃61; 2&＃xff09;&＃xff0c;以此类推。该图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点&＃xff08;值为 1&＃xff09;。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

提示&＃xff1a;

1. 节点数不超过 100 。
2. 每个节点值 Node.val 都是唯一的&＃xff0c;1 <&＃61; Node.val <&＃61; 100。
3. 无向图是一个简单图&＃xff0c;这意味着图中没有重复的边&＃xff0c;也没有自环。
4. 由于图是无向的&＃xff0c;如果节点 p 是节点 q 的邻居&＃xff0c;那么节点 q 也必须是节点 p 的邻居。
5. 图是连通图&＃xff0c;你可以从给定节点访问到所有节点。

解题方法

1. 这一题的主要问题是存在环&＃xff0c;如果不解开环的话&＃xff0c;必然会循环调用
2. 为了解开环&＃xff0c;因为题目里指明了 node.val 是独一无二的&＃xff0c;用一个 map 来存储&＃xff0c;key 值就是 node.val&＃xff0c;在往下遍历前&＃xff0c;先把当前元素存入 map 中

class Solution {Map map &＃61; new HashMap<>();public Node cloneGraph(Node node) {if (node &＃61;&＃61; null) return null;if (map.get(node.val) !&＃61; null) return map.get(node.val);ArrayList neighbors &＃61; new ArrayList<>();map.put(node.val, new Node(node.val, neighbors));for (int i &＃61; 0; i }


执行耗时:33 ms,击败了97.89% 的Java用户
内存消耗:38.7 MB,击败了95.85% 的Java用户