[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

Popular posts from this blog

Alpha Camp 全端開發課程學習心得

-
我喜歡邏輯，在哲學系求學時期，我花最多時間的科目，是形式邏輯。但是我一直不明白這個我相對擅長的科目，到底能用在什麼地方。我的邏輯能力，並沒有好到足夠讓我走上學術研究的路，那麼，或許我可以試著寫程式？ 學生時期的我，自認沒有錢，但是有時間。捨不得花錢去上程式設計課程，寧願自己找資源學習。去上過一些免費的程式入門課程，c++ 和 python，對我而言不是很難，但是學完之後，我還是看不出來，要怎麼靠學到的東西解決生活中遇到的問題，漸漸地就沒有動力繼續學下去。 直到出社會，存了點錢，也漸漸體會到時間的重要，終於捨得花錢投資自己，到 Alpha Camp 上專業的課程，而不是無頭蒼蠅自己亂找一通，省下許多時間，也看到自己學的東西是真的能用的，讓我有動力繼續學下去。 我還記得學到串接 api 的時候，心裡真是太激動了。以前在學免費課程時，就隱約有種「我寫的程式，範圍只侷限在我的電腦上」的貧瘠感覺，而在知道了 api 後，發現「我寫的程式可以跟世界接上線了」，頓時覺得自己非常富有。不過，後來才知道，串別人的 api 服務通常是要付費的。 大概是受了形式邏輯的影響，我在學習程式語言時，總是試圖去辨認，哪些東西是比較基本的，基本的東西是透過什麼樣的規則組合出複雜的東西。例如，變數、array、for 迴圈和 function 是基本的東西，可以用這些基本的東西組合出 array 的 reduce 方法，像這樣： function mimicReduce(array, reducerFunction, initialValue) {     if (initialValue) {         let accumulator = initialValue         for (let i = 0; i < array.length; i++) {             accumulator = reducerFunction(accumulator, array[i])         }         return accumulator     } else {         let accumulator = array[0]         for (let i = 1; i < array.length; i
Read more

在 javascript 用 regular expression 為金額加上千位數分隔符號

-
 為了方便使用者快速判斷金額，所以想加上千位數分隔符號。例如： 3000 --> 3,000 3000000 --> 3,000,000 搜尋資料後，結論： 如果數字有小數點的話，可以用  const amount = '3000.00' amount.replace(/\B(?<!\.\d*)(?=(\d{3})+(?!\d))/g, ',') 參考資料： Javascript之數值千分位符號（Comma）的顯示 如果沒有小數點的話，可以用  const amount = '3000' amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',') 參考資料： [Javascrpt]轉換數字成含千分位的文字   不過這個鬼畫符的語法我完全看不懂，查資料的時候一度不肯相信這是真正的程式碼呢⋯⋯因緣際會在讀書會中，得到 Helix 同學提示的關鍵字「 regular expression」，決定試著弄懂，「amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',')」到底是什麼意思。 一、 String.prototype.replace() - MDN 範例：我不小心把 world 拼成 word，想要把句子裡所有的 word 都替換成  world。 const text = 'Hello word! Hello word!' console.log(text.replace('word', 'world')) 結果印出 Hello world! Hello word! 很不幸地，只有第一個錯字有替換，其他錯字都被放生了。如果想要替換全部的 word，就要這樣寫： const text = 'Hello word! Hello word!' console.log(text.replace( /word/ g , ' world '))
Read more

shop_platform - sqlalchemy.exc.TimeoutError

-
發生的問題 啟動伺服器後，第二十一次請求「需要查詢資料庫」的頁面時，會出現「sqlalchemy.exc.TimeoutError: QueuePool limit of size 10 overflow 10 reached, connection timed out, timeout 30.00 (Background on this error at: https://sqlalche.me/e/14/3o7r )」的錯誤訊息。如果請求是不需要查詢資料庫的（例如靜態檔案或前往登入頁面），就不會發生此錯誤。 把 size 和 overflow 設定成更小的數字，可以更快重現這個錯誤 。 感覺起來，就像查詢完資料庫以後，沒有把 connection 釋出一樣，導致「size + overflow」是多少，就只能查詢多少次資料庫。 發現瀏覽器每向伺服器請求一次「需要查詢資料庫」的頁面，在 MySQL Workbench 用 show PROCESSLIST; 指令的查詢結果就會多出一筆資料，筆數達到 size + overflow 時，若再次請求「需要查詢資料庫」的頁面，就會噴 QueuePool limit of size 10 overflow 10 reached 的錯誤。關閉伺服器時，那幾筆資料才會被刪除。 嘗試過但失敗的方法 app.run(debug=False) 自己註冊一個關閉 session 的函式 @app.teardown_appcontext # 改成 @app.teardown_request 也沒用 def teardown_db(exception): db.session.remove() # 改成 db.session.close() 也沒用 print('***** session.remove') # 這一行有印出來，所以此函式有被執行 把 FLASK_ENV=development 拿掉 ，於是 FLASK_ENV 變成預設的 production app.config["SQLALCHEMY_COMMIT_ON_TEARDOWN"] = True 終於成功的方法 第一種方法：用 Ap
Read more