DFS應用題 重建陣列 Restore the Array From Adj Pairs_Leetcode #1743

閱讀時間約 6 分鐘
raw-image

這題的題目在這裡:Restore the Array From Adjacent Pairs

題目敘述

題目會給我們一個pair陣列,裡面都是原本陣列相鄰元素形成的pair,順序已經被打散。

要求我們從pair陣列重建出原本的陣列。

答案可能有不只一組,任選一組回傳即可。


測試範例

Example 1:

Input: adjacentPairs = [[2,1],[3,4],[3,2]]
Output: [1,2,3,4]
Explanation: This array has all its adjacent pairs in adjacentPairs.
Notice that adjacentPairs[i] may not be in left-to-right order.

Example 2:

Input: adjacentPairs = [[4,-2],[1,4],[-3,1]]
Output: [-2,4,1,-3]
Explanation: There can be negative numbers.
Another solution is [-3,1,4,-2], which would also be accepted.

Example 3:

Input: adjacentPairs = [[100000,-100000]]
Output: [100000,-100000]

約束條件

Constraints:

  • nums.length == n
  • adjacentPairs.length == n - 1
  • adjacentPairs[i].length == 2
  • 2 <= n <= 10^5
  • -10^5 <= nums[i], ui, vi <= 10^5
  • There exists some nums that has adjacentPairs as its pairs.

演算法

其實相鄰的pair就對應到圖論中的兩條指向邊

一條是u->v,另一條是v->u。

u,v就對應到pair裡面的兩個數字。

舉例來說

Given adjacentPairs = [[2,1],[3,4],[3,2]]

Corresponding graph in G

1 <-> 2 <-> 3 <-> 4

[2,1]就代表有一條指向邊1->2 和 另一條指向邊 2->1

[3,4]就代表有一條指向邊3->4 和 另一條指向邊 4->3

[3,2]就代表有一條指向邊3->2 和 另一條指向邊 2->3


如果,從端點1出發,那麼DFS走完整張圖的結果是1->2->3->4

可以還原出陣列[1,2,3,4]


如果,從端點4出發,那麼DFS走完整張圖的結果是4->3->2->1

可以還原出陣列[4,3,2,1]


兩個都是對的答案,任選其中一組回傳即可。


用pair重建整個graph,以adjacency list的形式儲存起來。

接著,以端點(只出現一次的數值)為出發點,用DFS走訪整張圖,途中經過的路徑,就是還原後的答案,也就是重建好的原始陣列


程式碼

class Solution:
 def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:

  graph = defaultdict(list)

  # update adjacent list in Graph G
  for u, v in adjacentPairs:
   graph[u].append(v)
   graph[v].append(u)
  
  array = []

  # Locate starting node whose occurrence = 1
  start = next(x for x in graph if len(graph[x]) == 1)

  def dfs(node, prev):

   # Restore array element   
   array.append(node)

   # DFS to next neighbor, and never go back
   for neighbor in graph[node]:
    if neighbor != prev:
     dfs(neighbor, node)

   return
  # ================================

  # Launch DFS from starting node
  dfs(node=start, prev=None)
  return array

複雜度分析

時間複雜度:

O(n) DFS拜訪整張圖 = O(V)+ O(E) = O(n)。

建Graph的時間成本 = 掃描 adjacentPairs 的成本 = O(n)

空間複雜度:

O(n) DFS拜訪整張圖 = O(V) = O(n)。

建Graph的空間成本 = graph 這張表的成本 = O(2n) = O(n)


關鍵知識點

聯想到其實相鄰的pair就對應到圖論中的兩條指向邊

一條是u->v,另一條是v->u。

u,v就對應到pair裡面的兩個數字。

舉例來說

Given adjacentPairs = [[2,1],[3,4],[3,2]]

Corresponding graph in G

1 <-> 2 <-> 3 <-> 4

[2,1]就代表有一條指向邊1->2 和 另一條指向邊 2->1

[3,4]就代表有一條指向邊3->4 和 另一條指向邊 4->3

[3,2]就代表有一條指向邊3->2 和 另一條指向邊 2->3


Reference:

[1] Python O(n) by DFS [w/ Demo] - Restore the Array From Adjacent Pairs - LeetCode

avatar-img
90會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
題目會給定我們兩個點座標,分別是起點和終點。 另外,還有一個參數t,代表時間限制。 從起點出發之後,每一秒鐘,我們必須選擇一個N8 8連通的方向,往鄰居的格子點移動。(題目有特別強調,每一秒必須強制移動到下一個格子點,不能停留在原地) 請問我們能不能在時間限制內,從起點走到終點?
題目會給一顆二元樹,要求我們計算節點值 和 子樹平均值相等的node有幾個。
題目會給我們一顆二元樹的根結點,要求我們找出每一層最大的節點值。
題目會給我們節點總數目n、左子樹的關係陣列、右子樹的關係陣列,要求我們驗證在給定的條件下,能不能構成一顆合法的二元樹。
題目會給我們兩條已經從小到大排序好的串列,要求我們依照從小到大的順序,合併這兩條串列。
題目的輸入會給我們一個串列,要求我們從頭到尾反轉整個串列。 例子: 如果輸入是1 -> 2 -> 3,那麼輸出就是 3 -> 2 -> 1
題目會給定我們兩個點座標,分別是起點和終點。 另外,還有一個參數t,代表時間限制。 從起點出發之後,每一秒鐘,我們必須選擇一個N8 8連通的方向,往鄰居的格子點移動。(題目有特別強調,每一秒必須強制移動到下一個格子點,不能停留在原地) 請問我們能不能在時間限制內,從起點走到終點?
題目會給一顆二元樹,要求我們計算節點值 和 子樹平均值相等的node有幾個。
題目會給我們一顆二元樹的根結點,要求我們找出每一層最大的節點值。
題目會給我們節點總數目n、左子樹的關係陣列、右子樹的關係陣列,要求我們驗證在給定的條件下,能不能構成一顆合法的二元樹。
題目會給我們兩條已經從小到大排序好的串列,要求我們依照從小到大的順序,合併這兩條串列。
題目的輸入會給我們一個串列,要求我們從頭到尾反轉整個串列。 例子: 如果輸入是1 -> 2 -> 3,那麼輸出就是 3 -> 2 -> 1
你可能也想看
Google News 追蹤
Thumbnail
這個問題「Remove Duplicates from Sorted Array」要求我們從一個已排序的陣列中移除重複的元素,並且返回移除後的陣列新長度。由於陣列已經是排序好的,所以所有的重複元素會是相鄰的。 我們需要移除重複的元素,使每個元素最多只出現一次,並返回去重後的陣列長度。不能使用額外的空
Thumbnail
這篇內容,將會講解什麼是陣列,以及與陣列相關的知識。包括陣列的簡介、陣列的資料限制、陣列的維度、一維陣列、二維陣列。
Thumbnail
這篇文章介紹了排列和組閤中的錯位排列和排容原理,並提供了一種相對樸實的解題方法。透過例子詳細解釋了選擇情況下的數學原理,讓讀者能夠理解並吸收。文章通過課堂上難以推敲的題目,提出了一個相對簡單的方式來解題。 圖片選自@pngtree
Thumbnail
分享在網路上看到的陣列題目。通常 for...of 的 value 是陣列中的每個值,那如果我們在迭代中對陣列操作會發生什麼事? 題目來源:https://x.com/_jayphelps/status/1774640511158022335?s=20
今天要來嘗試的是,如何不用好用的Array.map 方法,來實現 Array.map 的功能。 What is Array.map map() 方法會建立一個新的陣列,其內容為原陣列的每一個元素經由回呼函式運算後所回傳的結果之集合。 簡單來說就是把陣列內的每一個值,個別跑函式,把新的值回傳出成
Thumbnail
最近每天都有同學在解題社群提問這類型的問題,有些同學甚至po出解答來提問,表示看了解答卻還是看不懂,畢竟有時候「詳解」也沒辦法完整表達所有觀念。 排列組合是一門龐大的章節,許多人聞排組而色變,但排列組合的本質其實還是「窮舉法」,也就是把全部的可能通通列出來,只是很多地方我們可以透過計算讓窮舉變得更
Thumbnail
這個問題「Remove Duplicates from Sorted Array」要求我們從一個已排序的陣列中移除重複的元素,並且返回移除後的陣列新長度。由於陣列已經是排序好的,所以所有的重複元素會是相鄰的。 我們需要移除重複的元素,使每個元素最多只出現一次,並返回去重後的陣列長度。不能使用額外的空
Thumbnail
這篇內容,將會講解什麼是陣列,以及與陣列相關的知識。包括陣列的簡介、陣列的資料限制、陣列的維度、一維陣列、二維陣列。
Thumbnail
這篇文章介紹了排列和組閤中的錯位排列和排容原理,並提供了一種相對樸實的解題方法。透過例子詳細解釋了選擇情況下的數學原理,讓讀者能夠理解並吸收。文章通過課堂上難以推敲的題目,提出了一個相對簡單的方式來解題。 圖片選自@pngtree
Thumbnail
分享在網路上看到的陣列題目。通常 for...of 的 value 是陣列中的每個值,那如果我們在迭代中對陣列操作會發生什麼事? 題目來源:https://x.com/_jayphelps/status/1774640511158022335?s=20
今天要來嘗試的是,如何不用好用的Array.map 方法,來實現 Array.map 的功能。 What is Array.map map() 方法會建立一個新的陣列,其內容為原陣列的每一個元素經由回呼函式運算後所回傳的結果之集合。 簡單來說就是把陣列內的每一個值,個別跑函式,把新的值回傳出成
Thumbnail
最近每天都有同學在解題社群提問這類型的問題,有些同學甚至po出解答來提問,表示看了解答卻還是看不懂,畢竟有時候「詳解」也沒辦法完整表達所有觀念。 排列組合是一門龐大的章節,許多人聞排組而色變,但排列組合的本質其實還是「窮舉法」,也就是把全部的可能通通列出來,只是很多地方我們可以透過計算讓窮舉變得更