Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2023-04-08 13:59:21
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:
作者: JIWP (JIWP)   2023-04-08 14:01:00
大師
作者: pandix (麵包屌)   2023-04-08 14:15:00
大師
作者: Che31128 (justjoke)   2023-04-08 14:44:00
大師

Links booklink

Contact Us: admin [ a t ] ucptt.com