Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

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
推 JIWP: 大師
推 pandix: 大師
→ Che31128: 大師
推 NTHUlagka: 大師