前往
大廳
主題

LeetCode - 2359. Find Closest Node to Given Two Nodes 解題心得

Not In My Back Yard | 2023-06-17 12:00:08 | 巴幣 102 | 人氣 137

題目連結:


題目意譯:
你被給定一個有著編號為 0 到 n - 1 的 n 個節點之有向圖,其中每個節點有最多一個向外的邊。

該圖以一個給定的索引值從 0 開始且大小為 n 的之陣列 edges,代表著存在一條邊從節點 i 到節點 edges[i]。如果節點 i 沒有往外的邊,則 edges[i] == -1。

你同時也被給定兩整數 node1 和 node2。

回傳可以同時從 node1 和 node2 這兩個節點抵達的節點之索引值,使得「node1 到該節點的距離」與「node2 到該節點的距離」之最大值盡可能地小。如果有多個可能的答案,則回傳當中最小的索引值。而如果不存在這樣子的節點,則回傳 -1。

注意 edges 可能包含著環。

限制:
n == edges.length
2 ≦ n ≦ 10 ^ 5
-1 ≦ edges[i] < n
edges[i] != i
0 ≦ node1, node2 < n



範例測資:
範例 1:
輸入: edges = [2,2,3,-1], node1 = 0, node2 = 1
輸出: 2
解釋: 節點 0 到節點 2 的距離是 1,而節點 1 到節點 2 的距離是 1。
這兩個距離的最大值為 1。可以證明不存在任何節點可以得到比 1 更小的最大距離。因此我們回傳節點 2。

範例 2:
輸入: edges = [1,2,-1], node1 = 0, node2 = 2
輸出: 2
解釋: 節點 0 到節點 2 的距離是 2,而節點 2 到自己本身的距離是 0。
這兩個距離的最大值為 2。可以證明不存在任何節點可以得到比 2 更小的最大距離。因此我們回傳節點 2。


解題思維:
就單純地從 node1 和 node2 各自走到它們可以走到的節點即可,直到走不了或是看到先前走過的節點為止。

少數深度優先搜尋(Depth First Search,DFS)和廣度優先搜尋(Breadth First Search,BFS)的探訪順序長一模一樣的題型,因為每個節點最多只會到一個新的節點。

最後只要比較那些同時被 node1 和 node2 走到的節點之於兩者的距離值來比較哪個節點的最大距離值比較小即可(如果有一樣的情況則取索引值小的)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作