LeetCode Digest
4 分鐘 閱讀文 (大約 549 個字)

133. Clone Graph

題目
思路：

  1. 可以找到最小可重複動作嗎？
    • 題目的 method 要傳入 first node, 回傳它的 clone
    • 最小可重複動作可設定為：給定一個 node, 回傳 its clone
  2. DFS: 先寫 recursive case
  3. Base case: method 收到已 clone 過的 node
    • Use a dict to record nodes been cloned.
  4. 須注意傳入 cloneGraph 的 node 有可能是 None
Python3 solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

from typing import Optional
class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        old_new_map = {}
        
        def clone_node(node):
            # Base case
            if node in old_new_map:
                return old_new_map[node]
        
            # Recursive case
            clone = Node(node.val)
            old_new_map[node] = clone
            for neighbor in node.neighbors:
                clone.neighbors.append(clone_node(neighbor))        
            return clone
            
        return node and clone_node(node)

How to do it with BFS?

思路

  1. 一開始的直覺想法是就照 DFS 的套路，只是改成 recursive case 在迴圈裡做，也就是說把要執行最小可重複動作的 node 放入 stack 讓他在之後的迴圈去做 recursive case
    • 上面的 recursive case: clone 自己，也 clone 自己的所有 neighbors 並加到我的 clone 的 neighbors
  2. 發現問題：那些 neighbors 繼續丟進 stack 想重複一樣的動作時，發現會 clone 兩次，表示這個動作拆的不好
  3. 修改最小可重複動作：我先 clone 好自己，最小可重複動作改成 clone 我的 neighbors 並加入我 clone 的 neighbors，這樣就不會 clone 兩次了，所有加入 stack 的 node 都是已經 clone 過的
  4. clone 前先檢查 base case：假如這個 neighbor 有在 old_to_new 裡，代表他已經有被 clone 過了，而且也有被加入過 stack，所以不用再 clone & add to stack，但還是要把他的 clone add to neighbors，因為一個點可能同時是好幾個點的鄰居，所以當然有可能被加好幾次鄰居
Python3 solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
    if not node:
        return None

    stack = [node]
    old_to_new = {node: Node(node.val)}
    while stack:
        n = stack.pop()
        for neighbor in n.neighbors:
            if neighbor not in old_to_new:
                n_clone = Node(neighbor.val)
                old_to_new[neighbor] = n_clone
                stack.append(neighbor)
            old_to_new[n].neighbors.append(old_to_new[neighbor])

    return old_to_new[node]
# , , ,
Redo Logs in Database Systems
1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

評論

分類

標籤雲

android array authentication binary search binary search tree binary tree bit manipulation breadth-first search database depth-first search distributed system django docker dokku dynamic programming graph greedy hash table heap heroku java jwt linked list matrix mysql paas package management pipenv postgresql python recursion shortest path simulation sliding window sorting stack string tree two pointers

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×