LeetCode: Find The Town Judge

  • 1 minute de citit
  • 1 exemplu de cod

Disponibil și în English

Salut

În acest articol vă prezint soluția mea în Python3 pentru următoarea problemă, pe care am găsit-o pe LeetCode: find-the-town-judge.

Notă: Soluția se află pe a doua pagină, așa că nu veți fi spoilerizați dacă vreți să încercați să rezolvați problema singuri. Distracție plăcută!

from collections import defaultdictfrom typing import List"""Într-un oraș, există N persoane etichetate de la 1 la N.Există un zvon conform căruia una dintre aceste persoane este, în secret, judecătorul orașului.Dacă judecătorul orașului există, atunci:    Judecătorul orașului nu are încredere în nimeni.    Toată lumea (cu excepția judecătorului orașului) are încredere în judecătorul orașului.    Există exact o persoană care satisface proprietățile 1 și 2.Vi se dă trust, un tablou de perechi trust[i] = [a, b] care reprezintă faptul că persoana etichetată aare încredere în persoana etichetată b.Dacă judecătorul orașului există și poate fi identificat, returnați eticheta judecătorului orașului. Altfel, returnați -1."""class Solution:    def _filterForJudge(self, N, trust_dict):        no_trustees = None        for i in range(1, N + 1):            person_trusted = trust_dict.get(i, set())            if len(person_trusted) == 0:                if no_trustees is None:                    no_trustees = i                else:                    return None        return no_trustees    def findJudge(self, N: int, trust: List[List[int]]) -> int:        trust_dict = defaultdict(set)        for i in trust:            trust_dict[i[0]].add(i[1])        # Judecătorul orașului nu are încredere în nimeni.        no_trustee = self._filterForJudge(N, trust_dict)        if no_trustee:            # Toată lumea are încredere în judecătorul orașului.            people_who_trust = 0            for p in trust_dict.items():                # Verificăm dacă persoana are încredere în judecătorul orașului.                if no_trustee in p[1]:                    people_who_trust += 1            if people_who_trust == N-1:                return no_trustee        return -1if __name__ == '__main__':    s = Solution()    print(s.findJudge(2, [[1,2]]))    print(s.findJudge(3, [[1,3],[2,3]]))    print(s.findJudge(3, [[1,3],[2,3],[3,1]]))    print(s.findJudge(3, [[1,2],[2,3]]))    print(s.findJudge(4, [[1,3],[1,4],[2,3],[2,4],[4,3]]))

Mulțumesc pentru lectură!