LeetCode | 997.找到小镇的法官

本文主要是介绍LeetCode | 997.找到小镇的法官，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

这道题拿到后很明显是一个图论的简单出度入度问题，法官的标志就是图中出度为0，入度为n-1的结点，而且根据题目条件，满足这一条件的结点有且只有一个
但是我不知道力扣中关于图论的邻接表和邻接矩阵这些数据结构是需要自己写还是已经有现有的，我就自己写了个邻接表的类，然后根据条件返回法官结点，自然，多写了这么多代码，运行时间直接加倍，我直接垫底了555

class GraphAdjList:def __init__(self):self.graph = {}def add_vertex(self, vertex):if vertex not in self.graph:self.graph[vertex] = []def add_edge(self, vertex1, vertex2):if vertex1 in self.graph and vertex2 in self.graph:self.graph[vertex1].append(vertex2)def out_degree(self, vertex):if vertex in self.graph:return len(self.graph[vertex])return 0def in_degree(self, vertex):count = 0for v in self.graph:if vertex in self.graph[v]:count += 1return countdef __str__(self):return str(self.graph)class Solution(object):def findJudge(self, n, trust):""":type n: int:type trust: List[List[int]]:rtype: int"""g = GraphAdjList()for i in range(n):g.add_vertex(i + 1)for numList in trust:g.add_edge(numList[0], numList[1])for i in range(n):if g.in_degree(i+1) == n-1 and g.out_degree(i+1) == 0:return i+1return -1

在这里插入图片描述
但是看了题解，好像并没有用到邻接表这种数据结构，但是思想是一样的思想的，也是图论那一套，但是用的Counter()函数，Counter 是 Python 的 collections 模块中的一个类，用于计数哈希对象。它是一个字典的子类，旨在提供一种便捷的方式来计数可哈希对象的数量。简直不要太妙！涨知识了！

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)