ETH官方钱包

前往
大廳
主題

LeetCode - 2374. Node With Highest Edge Score 解題心得

Not In My Back Yard | 2023-06-29 12:00:04 | 巴幣 0 | 人氣 121

題目連結(jié):


題目意譯:
你被給定一個有著 n 個節(jié)點其編號為 0 到 n - 1 的有向圖,其中每個節(jié)點恰好有一條向外的邊。

該圖以一個索引值從 0 開始且長度 n 的整數(shù)陣列給定,其中 edges[i] 代表著有一條邊從節(jié)點 i 導(dǎo)向至節(jié)點 edges[i]。

節(jié)點 i 的「邊分數(shù)」定義為所有有著一條邊指向 i 的節(jié)點之編號之總和。

回傳有著最高邊分數(shù)的節(jié)點。如果有多個節(jié)點有著相同的邊分數(shù),則回傳索引值最小者。

限制:
n == edges.length
2 ≦ n ≦ 10 ^ 5
0 ≦ edges[i] < n
edges[i] != i



範例測資:
範例 1:
輸入: edges = [1,0,0,0,0,7,7,5]
輸出: 7
解釋:
節(jié)點 1 、 2 、 3 和 4 各有一條邊指向節(jié)點 0。節(jié)點 0 的邊分數(shù)為 1 + 2 + 3 + 4 = 10。
節(jié)點 0 各有一條邊指向節(jié)點 1。節(jié)點 1 的邊分數(shù)為 0。
節(jié)點 7 各有一條邊指向節(jié)點 5。節(jié)點 5 的邊分數(shù)為 7。
節(jié)點 5 和 6 各有一條邊指向節(jié)點 7。節(jié)點 7 的邊分數(shù)為 5 + 6 = 11。
節(jié)點 7 有著最高的邊分數(shù)值,所以回傳 7。

範例 2:
輸入: edges = [2,0,0,2]
輸出: 0
解釋:
節(jié)點 1 和 2 各有一條邊指向節(jié)點 0。節(jié)點 0 的邊分數(shù)為 1 + 2 = 3。
節(jié)點 0 和 3 各有一條邊指向節(jié)點 2。節(jié)點 2 的邊分數(shù)為 0 + 3 = 3。
節(jié)點 0 和 2 都有著邊分數(shù)值 3。由於節(jié)點 0 的索引值較小,我們回傳 0。


解題思維:
就掃過一次 edges,然後看哪些節(jié)點出現(xiàn)最多次即可(方式很多:可以直接統(tǒng)計再看哪個編號最多;也可以排序後,使得相同編號聚在一起,然後再統(tǒng)計)。




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

創(chuàng)作回應(yīng)

追蹤 創(chuàng)作集

作者相關(guān)創(chuàng)作

更多創(chuàng)作