前往
大廳
主題

LeetCode - 997. Find the Town Judge 解題心得

Not In My Back Yard | 2021-03-03 01:19:48 | 巴幣 2 | 人氣 572

題目連結:


題目意譯:
在一個城鎮中,有著 N 個人編號為 1 到 N 。有個謠言傳說其中一人為秘密的城鎮法官。

如果城鎮法官存在,則
1. 城鎮法官不信任任何人。
2. 所有人(除了城鎮法官)信任著城鎮法官。
3. 只有唯一一個人滿足性質 1 和 2 。

給定你陣列 trust,其為一數對陣列 trust[i] = [a, b] 代表著編號 a 的人信任著編號 b 的人。

如果城鎮法官存在且可以被找出,回傳城鎮法官之編號。反之,回傳 -1 。

限制:
1 ≦ N ≦ 1000
0 ≦ trust.length ≦ 10^4
trust[i].length == 2
trust[i] 皆相異。
trust[i][0] != trust[i][1]
1 ≦ trust[i][0] 、 trust[i][1] ≦ N



範例測資:
範例 1:
輸入: N = 2, trust = [[1,2]]
輸出: 2

範例 2:
輸入: N = 3, trust = [[1,3],[2,3]]
輸出: 3

範例 3:
輸入: N = 3, trust = [[1,3],[2,3],[3,1]]
輸出: -1

範例 4:
輸入: N = 3, trust = [[1,2],[2,3]]
輸出: -1

範例 5:
輸入: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
輸出: 3


解題思維:
因為法官不信任任何人,但是其他人都信任他,所以我們可以用一個布林陣列 T[i] 代表編號 i 的人有沒有信任任何人,以及一個整數陣列 C[i] 代表編號 i 被多少人信任著。

當有一個編號 i 滿足 T[i] 為 0 且 C[i] 為 N - 1 ,即代表編號 i 這個人是法官,所以回傳 i;但是如果有多個或是沒有這樣子的人,則代表法官不存在,因此回傳 -1。




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

創作回應

更多創作