Posted on 2023-01-23 23:42
Uriel 閱讀(64)
評論(0) 編輯 收藏 引用 所屬分類:
閑來無事重切Leet Code 、
大水題
鎮上一共n個人，給出一些trust pair，trust[i]=[a
i, b
i]，表示a
i信任b
i，鎮上有一位法官，法官被所有人信任，且不信任任何人，如果可以通過這些trust pair判斷第幾個人是法官，則輸出，否則輸出-1
用fg_be_trusted標記每個人被幾個人信任，fg_trust標記每個人信任幾個其他人，如果法官存在，則fg_trust[i]=0，fg_be_trusted[i]=n-1
1 #997
2 #Runtime: 1407 ms (Beats 26.42%)
3 #Memory: 18.5 MB (Beats 91.6%)
4
5 class Solution(object):
6 def findJudge(self, n, trust):
7 """
8 :type n: int
9 :type trust: List[List[int]]
10 :rtype: int
11 """
12 fg_trust = [0] * (n + 1)
13 fg_be_trusted = [0] * (n + 1)
14 for i,j in trust:
15 fg_be_trusted[j] += 1
16 fg_trust[i] += 1
17 cnt = 0
18 for i in range(1, n + 1):
19 if fg_trust[i] == 0 and fg_be_trusted[i] == n - 1:
20 cnt += 1
21 fg = i
22 if cnt == 1:
23 return fg
24 return -1