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