Leetcode 997 Find the Town Judge

发表于 |

在一座小镇中，有N个人，编号为1到N。现在在这N个人中可能存在着一位法官。
如果法官确实存在的话，那么将会满足以下条件：

  1. 法官不相信任何一个人
  2. 除法官外的每个人都相信法官
  3. 只有一位法官会满足上述条件

现在给定一个trust， trust[i] = [a,b]表示编号为a的人相信编号为b的人。
如果法官确实存在，请返回这个法官的编号，若不存在，则返回-1.

题意分析：
这道题需要我们找到一个法官，这个法官呢不相信任何人，而其他的所有人都必须相信这个法官
那么转成图问题就是，找到一个点，这个点的入度恰好为N-1（总共N个人），出度为0

这里使用一个flag数组代表该点是否有出度，用degree数组表示这个点的入度

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def findJudge(self, N, trust):
        degree = [0] * (1+N)
        flag = [0] * (1+N)
        for a,b in trust:
            flag[a] = -1
            degree[b] += 1
        
        for i in range(1, N+1):
            if degree[i] == N-1 and flag[i] != -1:
                return i
        return -1