当前位置：首页 > news >正文

leetcode997. 找到小镇的法官，同样的思路，被佬的操作秀到了_图篇

news 来源：原创 2024/9/21 14:31:31

题目

小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。

如果小镇法官真的存在，那么：

小镇法官不会信任任何人。
每个人（除了小镇法官）都信任这位小镇法官。
只有一个人同时满足属性 1 和属性 2 。
给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。

如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -1 。

示例 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

思路

作为一个简单题，它本“不配”出现在我的总结文章里，奈何大佬操作第一次见，忍不住给它一个出场秀。

首先这题思路很简单，就是判断每个点的入度和出度，法官就是入度为n-1出度为0的点。用的是哈希。

代码

贴出我的代码：

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        # 这是一个有向图 找到入度为n-1 出度为0的点
        # 点：[入度，出度]
        dic = {i+1 : [0,0] for i in range(n)}
        for i in range(len(trust)):
            key1, key2 = trust[i][0], trust[i][1]
            dic[key1][1] += 1
            dic[key2][0] += 1  
        for k in dic:
            if dic[k][0] == n-1 and dic[k][1] == 0:
                return k
        return -1

贴出官方题解的三行代码：

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        inDegrees = Counter(y for _, y in trust)
        outDegrees = Counter(x for x, _ in trust)
        return next((i for i in range(1, n + 1) if inDegrees[i] == n - 1 and outDegrees[i] == 0),  -1)