Day2 997. 找到小镇的法官

差不多懂了

image.png
题目:
小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。
如果小镇法官真的存在，那么：

  1. 小镇法官不会信任任何人。
  2. 每个人（除了小镇法官）都信任这位小镇法官。
  3. 只有一个人同时满足属性 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 <= n <= 1000
  • 0 <= trust.length <= 104
  • trust[i].length == 2
  • trust 中的所有trust[i] = [ai, bi] 互不相同
  • ai != bi

  • 1 <= ai, bi <= n

    放一个cv答案在这里

    1. class Solution:
    2.   def findJudge(self, n: int, trust: List[List[int]]) -> int: 
    3.       t = [set() for _ in range(n)]
    4.       for a, b in trust:                 #建立信任的人的集合的列表
    5.           t[a-1].add(b)                  
    7.       possiblePerson = []                #可能是法官的人
    8.       for i in range(n):
    9.           if len(t[i]) == 0:
    10.               possiblePerson.append(i)
    12.       for k in possiblePerson:           #如果有一个人不信任他，那他就不是法官
    13.           isJudge = True
    14.           for i in range(n):
    15.               if i != k:
    16.                   if k+1 not in t[i]:
    17.                       isJudge = False
    18.                       break
    19.           if isJudge:
    20.               return k+1
    21.       return -1

    摘抄其他思路代码

    ```python class Solution: def findJudge(self, N: int, trust: List[List[int]]) -> int:

    1.   # a[i]表示第i个人的相信者的个数，入度数
    2.   # b[i]表示第i个人相信的人的个数，出度数
    3.   a = [0 for _ in range(n+1)]
    4.   b = [0 for _ in range(n+1)]
    6.   for x, y in trust:
    7.       a[y] += 1
    8.       b[x] += 1
    10.   for i in range(1, n+1):
    11.       if a[i] == n-1 and b[i] == 0:
    12.           return i
    14.   return -1
<a name="ujxDa"></a>
### 最终优化后的答案
```python
class Solution:
    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        a = [0 for x in range(N+1)] #相信你的人,加1的原因是小镇人员的编号是从1开始的
        b = [0 for x in range(N+1)] #你相信的人

        for num in trust:
            a[num[1]] += 1   #存储的为相信他的人
            b[num[0]] += 1   

        for i,num in enumerate(a):
            if(i!=0 and num == N-1): #所有人都相信法官
                if(b[i] == 0): #法官不相信任何人 这里就是用来确认 没有人是法官的情况
                    return i
        return -1

思路

  1. 就是用一个数组来存储所有人相信的人…
  2. 然后就是当某个人的票数为村民的人数的时候就是判断这个是法官 或者 没有人是法官的情况
  3. 妙…