Re: [閒聊] 每日LeetCode已回收
133. Clone Graph
給你一個圖形，返回一個深拷貝的克隆圖形，圖形的點定義如下：
class Node {
public int val;
public List<Node> neighbors;
}
Example：
https://assets.leetcode.com/uploads/2019/11/04/133_clone_graph_question.png
Input: adjList = [[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 = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
思路：
1.用dfs遍歷原Node。
2.遍歷的過程複製節點並把 (node -> clone) 的關係保存到map。
3.dfs的結束條件為：map已經複製過當前node，表示已經走過。
4.遍歷完返回最外層的clone node即可。
Java Code：
-------------------------------------------
class Solution {
private Map <Node,Node> visited = new HashMap<>();
public Node cloneGraph(Node node) {
if (node == null) {
return null;
}
if (visited.containsKey(node)) {
return visited.get(node);
}
Node clone = new Node(node.val);
visited.put(node, clone);
for (Node neighbor : node.neighbors) {
clone.neighbors.add(cloneGraph(neighbor));
}
return clone;
}
}
-------------------------------------------
--
https://i.imgur.com/bFRiqA3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1680933563.A.80D.html
※ 編輯: Rushia (122.100.75.86 臺灣), 04/08/2023 14:00:16
推
04/08 14:01,
2年前
, 1F
04/08 14:01, 1F
推
04/08 14:15,
2年前
, 2F
04/08 14:15, 2F
→
04/08 14:44,
2年前
, 3F
04/08 14:44, 3F
推
04/09 02:27,
2年前
, 4F
04/09 02:27, 4F
討論串 (同標題文章)
完整討論串 (本文為第 288 之 719 篇)：