[LeetCode] #133. Clone Graph
題目
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 value (int) and a list (List[Node]) of its neighbors.
直覺解
構想：
用 dictionary 儲存已經複製好的節點，因為節點的 val 和節點的編號是一樣的，所以就用 val 的值當作 key。用 waiting_stack 儲存待複製的節點。
while 迴圈：從 waiting_stack 裡拿出節點，先複製這個節點。然後迭代該節點的鄰居，把鄰居複製一份，把複製的鄰居 append 到 neighbors 裡；因為鄰居的鄰居還沒有被複製，所以需要把鄰居放進去 waiting_stack。
python 3 實作：
def cloneGraph(self, node: 'Node') -> 'Node':
if not node:
return None
def clone_node(node):
if not clonedNodes.get(node.val):
clonedNodes[node.val] = Node(node.val)
return clonedNodes[node.val]
clonedNodes = {}
waiting_stack = [node]
while waiting_stack:
current = waiting_stack.pop()
clone_node(current)
for neighbor in current.neighbors:
clone = clone_node(neighbor)
if clone not in clonedNodes[current.val].neighbors:
clonedNodes[current.val].neighbors.append(clone)
if not clone.neighbors and neighbor not in waiting_stack:
waiting_stack.append(neighbor)
return clonedNodes[1]
效能：
第一次
Runtime: 32 ms, faster than 93.99% of Python3 online submissions for Clone Graph.
Memory Usage: 14.6 MB, less than 81.03% of Python3 online submissions for Clone Graph.
第二次
Runtime: 40 ms, faster than 55.88% of Python3 online submissions for Clone Graph.
Memory Usage: 14.6 MB, less than 81.07% of Python3 online submissions for Clone Graph.
第三次
Runtime: 40 ms, faster than 55.88% of Python3 online submissions for Clone Graph.
Memory Usage: 14.6 MB, less than 55.80% of Python3 online submissions for Clone Graph.
犯過的錯誤
- 一開始設定成，凡是在 clonedNodes 裡出現過的節點，就不能放進 waiting_stack 裡。只被複製了 val，但 neighbors 還沒複製的節點，就沒被放進 waiting_stack 裡，導致有些節點的 neighbors 是 []。於是LeetCode 就一直提醒我「You must return a copy of all the nodes in the original graph」，我花了滿多時間才弄懂為什麼會出現這個提示。
- 把相同的節點重複放進 waiting_stack 裡，導致該節點的鄰居被重複 append。例如，本來鄰居是 [1, 2]，因為該節點在 waiting_stack 裡出現兩次，複製後，鄰居變成 [1, 2, 1, 2]
- 一度搞混了原始的節點和複製的節點。腦袋要再清醒一點，程式碼易讀性也需要再加強。
參考別人的解
來源：Fast, clear DFS python
構想：
用遞迴取代 waiting_stack
自己的 python 3 實作：
def cloneGraph(self, node: 'Node') -> 'Node':
def clone_node(node):
if not node:
return None
if cloned_nodes_dict.get(node.val):
return cloned_nodes_dict[node.val]
copy = Node(node.val)
cloned_nodes_dict[node.val] = copy
for neighbor in node.neighbors:
copy.neighbors.append(clone_node(neighbor))
return copy
cloned_nodes_dict = {}
return clone_node(node)
效能：
Runtime: 28 ms, faster than 98.83% of Python3 online submissions for Clone Graph.
Memory Usage: 14.6 MB, less than 55.80% of Python3 online submissions for Clone Graph.
研究別人的解
來源：Python BFS
研究感想：
乍看之下，覺得跟我的直覺解構想差不多，因為從 waiting_stack 裡面拿東西的方向不一樣，所以我是 DFS 而他的是 BFS。但是，為什麼他的程式碼那麼精簡，我的看起來就那麼厚重？
後來發現，我跟這個人寫法的差別，在於
每次的 while 迴圈，我都會複製一次 current 節點，但別人沒有這麼做。因為其他所有節點都可以用鄰居的關係連接到，所以真的不必像我那樣，每次都複製一次 current 節點。
-
1. 複製節點的鄰居時，我還需要多檢查鄰居有沒有重複。
2. 把節點放進 waiting_stack 前，我還需要多檢查該節點是否已經在 waiting_stack 裡面。
但別人只是巧妙地使用了 if nei not in clones: 這個判斷條件，就避免了上述兩個檢查在解決的問題。我因為把 if nei not in clones 的檢查封裝在另一個函式裡，所以沒辦法這樣做。
優化我的 python 3 實作：
def cloneGraph(self, node: 'Node') -> 'Node':
if not node:
return None
cloned = {}
cloned[node.val] = Node(node.val)
waiting_stack = [node]
while waiting_stack:
curr = waiting_stack.pop()
for neighbor in curr.neighbors:
if neighbor.val not in cloned:
cloned[neighbor.val] = Node(neighbor.val)
waiting_stack.append(neighbor)
cloned[curr.val].neighbors.append(cloned[neighbor.val])
return cloned[node.val]
效能：
第一次
Runtime: 36 ms, faster than 79.75% of Python3 online submissions for Clone Graph.
Memory Usage: 14.8 MB, less than 24.90% of Python3 online submissions for Clone Graph.
第二次
Runtime: 40 ms, faster than 55.88% of Python3 online submissions for Clone Graph.
Memory Usage: 14.8 MB, less than 24.90% of Python3 online submissions for Clone Graph.
第三次
Runtime: 40 ms, faster than 55.88% of Python3 online submissions for Clone Graph.
Memory Usage: 14.6 MB, less than 55.80% of Python3 online submissions for Clone Graph.
第四次
Runtime: 40 ms, faster than 55.88% of Python3 online submissions for Clone Graph.
Memory Usage: 14.5 MB, less than 93.54% of Python3 online submissions for Clone Graph.
第五次
Runtime: 40 ms, faster than 55.88% of Python3 online submissions for Clone Graph.
Memory Usage: 14.6 MB, less than 55.80% of Python3 online submissions for Clone Graph.
Comments
Post a Comment