Posted on 2023-01-23 23:42
Uriel 阅读(30)
评论(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