leetcode(力扣) 997. 找到小镇的法官 (剧本杀推理)

文章目录

• ​​题目描述：​​
• ​​思路分析​​
• ​​完整代码:​​

题目描述：

小镇里有 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

思路分析

这题的描述哈哈，你隔着打剧本杀呢？

题目说了一堆，最后要找到法官。

法官的属性就两句话： 1，不相信任何人 2.任何人都相信法官

就以上两个点遍历数组就行了。

• 先遍历一遍数组找到所有 有信任别人的人，则这个人就不可能是法官,添加到数组 ordi_p 中，遍历结束，如果ordi_p 等于题目所给的小镇人数n，则说明小镇中没有法官，直接返回-1.
• 然后我们再次遍历该数组，构造哈希表。key存可能的法官，val存信任该法官的人数。
• 最后我们遍历哈希表，法官必须有 n-1个人信任他，也就是说val必须等于n-1，并且还不能再前面的ordi_p数组中，符合条件既是答案。

完整代码:

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        if len(trust) == 0:
            if n == 1:
                return 1
            else:
                return -1
        hs = {}
        ordi_p = [] # 如果有相信的人, 则肯定不是法官
        for i in trust:
            ordi_p.append(i[0])
        if ordi_p == n:
            return -1
        print('这里是ordi_p',ordi_p)
        for i in trust:
            # key 存可能的法官， val存信任法官的人数
            if i[1] not in  hs:
                hs[i[1]] = 1
            else:
                hs[i[1]] +=1
        print('这里是hs',hs)
        # 法官需要有 n-1个人相信他
        for p in hs:
            if hs[p] == n-1 and p not in ordi_p:

                return p
        return -1