997. 找到小镇的法官

Posted on | In | |

小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。
如果小镇法官真的存在，那么：
小镇法官不会信任任何人。
每个人（除了小镇法官）都信任这位小镇法官。
只有一个人同时满足属性 1 和属性 2 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-the-town-judge
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个代码没有通过测试，因为碰到两个测试用例我觉得与题意相悖。题目输入包括n和trust，其数据格式如代码块中注释所示。有一个测试用例n=1，trust=[]。按照题干来说，法官要有人信他他才是法官，只有一个人时我个人理解他并不能算是法官。
第二个案例就是n=4，trust=[[1,3],[1,4],[2,3]]，答案为3。但4并未相信3，为什么3能为法官？这个案例哪怕脱离题干中“法官”的情景应该也过不去吧?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def findJudge(self, n, trust):
        """
        :type n: int
        :type trust: List[List[int]]
        :rtype: int
        """
        trust_dict = {i:[] for i in range(1,n+1)}
        trust_valid = list()
        for lst in trust:
            person_id,trusted_id = lst[0],lst[1]
            trust_dict[person_id].append(trusted_id)
        for i in trust_dict.values():
            trust_valid.extend(i)
        judger_id_maybe = min(trust_dict,key = trust_dict.get)
        
        if len(trust_dict[judger_id_maybe]) == 0 and len(trust_valid):
            for id,trust in trust_dict.items():
                if id == judger_id_maybe:
                    continue
                else:
                    if judger_id_maybe not in trust:
                        return -1
                    else:
                        return judger_id_maybe
        else:
            return -1

官方提供的代码如下，可是能过，呵呵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def findJudge(self, n, trust):
        """
        :type n: int
        :type trust: List[List[int]]
        :rtype: int
        """
        n = 4
        trust = [[1,3],[1,4],[2,3],[4,3]]
        inDegrees = Counter(y for _, y in trust)
        outDegrees = Counter(x for x, _ in trust)
        print(inDegrees)
        print("==============")
        print(outDegrees)
        return next((i for i in range(1, n + 1) if inDegrees[i] == n - 1 and outDegrees[i] == 0), -1)