欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode-Python-997. 找到小镇的法官

程序员文章站 2022-03-03 11:18:18
...

在一个小镇里,按从 1 到 N 标记了 N 个人。传言称,这些人中有一个是小镇上的秘密法官。

如果小镇的法官真的存在,那么:

  1. 小镇的法官不相信任何人。
  2. 每个人(除了小镇法官外)都信任小镇的法官。
  3. 只有一个人同时满足属性 1 和属性 2 。

给定数组 trust,该数组由信任对 trust[i] = [a, b] 组成,表示标记为 a 的人信任标记为 b 的人。

如果小镇存在秘密法官并且可以确定他的身份,请返回该法官的标记。否则,返回 -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

示例 4:

输入:N = 3, trust = [[1,2],[2,3]]
输出:-1

示例 5:

输入:N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
输出:3

 

提示:

  1. 1 <= N <= 1000
  2. trust.length <= 10000
  3. trust[i] 是完全不同的
  4. trust[i][0] != trust[i][1]
  5. 1 <= trust[i][0], trust[i][1] <= N

 

第一种思路:

爬起来做竞赛人还没清醒,用的是转成二维矩阵然后暴力解的方法。

正解应该是根据图的入度和出度。

class Solution(object):
    def findJudge(self, N, trust):
        """
        :type N: int
        :type trust: List[List[int]]
        :rtype: int
        """
        l = len(trust)
        if l < N-1:
            return -1
        check = [[0 for i in range(N)]  for j in range(N)]
        for pair in trust:
            check[pair[0] - 1][pair[1] - 1] = 1
            # print check
        # print check
        # for i in check:
            # print i
        for indexi, i in enumerate(check):
            flag = 0
            for indexj,j in enumerate(i):
                if j == 1:
                    flag = 1
                    break

            if flag == 0:
                judge = indexi + 1
                # print judge
                flagg = 0
                l = list()
                for k in range(N):
                    # print k, indexi
                    l.append(check[k][indexi])
                
                if l.count(0) == 1 and l.index(0) == indexi:
                    return judge
        return -1
                
            

第二种思路:

这是一道图论题,A信任B这个关系就可以抽象为A到B的一条有向路径,题目所求的就是是否只存在一个点,使得其他所有的点都有单向路径到这个点,而这个点无法到任何一个其他点。即找到一个入度为N-1, 出度为0的点。

开辟两个数组indegree和outdegree分别统计每个人的入度和出度,

根据trust数组往这两个数组里添加内容, trust[0]是出去的,trust[1]是进来的,

然后再从第一个人到第N个人遍历,如果有人被所有其他人信任(indegree[i] == N-1) 并且这个人谁都不相信(outdegree[i] == 0)就说明他可能是法官。

最后判断到底有几个人可能是法官,如果只有一个满足条件的法官,就返回他,否则返回 -1 。

class Solution(object):
    def findJudge(self, N, trust):
        """
        :type N: int
        :type trust: List[List[int]]
        :rtype: int
        """
        indegree = [0] * (N + 1)
        outdegree = [0] * (N + 1)
        
        res = list()
        
        for pair in trust:
            outdegree[pair[0]] += 1
            indegree[pair[1]] += 1
        
        for i in range(1, N + 1):
            if outdegree[i] == 0 and indegree[i] == N - 1:
                res.append(i)
        
        return res[0] if len(res) == 1 else -1

 

相关标签: