997. Find the Town Judge

leetcode easy

#array#csharp#easy#leetcode#search

Task

В городе есть n человек, помеченных от 1 до n. Ходят слухи, что один из этих людей тайно является городским судьей. Если городской судья существует, то: городской судья никому не доверяет. Все (кроме городского судьи) доверяют городскому судье. Существует ровно один человек, удовлетворяющий свойствам 1 и 2. Вам дан массив trust, где trust[i] = [ai, bi], представляющий, что человек, помеченный ai, доверяет человеку, помеченному bi. Если в массиве trust не существует доверительных отношений, то таких отношений не существует. Верните метку городского судьи, если городской судья существует и может быть идентифицирован, или верните -1 в противном случае.

Пример:

Input: n = 2, trust = [[1,2]]

Output: 2

C# solution

matched/original

public class Solution {
    public int FindJudge(int n, int[][] trust) {
        if (trust.Length == 0 && n == 1) {
            return 1;
        }
        int[] trustCount = new int[n + 1];
        int[] trustedBy = new int[n + 1];
        foreach (var t in trust) {
            trustCount[t[0]]++;
            trustedBy[t[1]]++;
        }
        for (int i = 1; i <= n; i++) {
            if (trustCount[i] == 0 && trustedBy[i] == n - 1) {
                return i;
            }
        }
        return -1;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int FindJudge(int n, int[][] trust) {
        if (trust.size() == 0 && n == 1) {
            return 1;
        }
        vector<int>& trustCount = new int[n + 1];
        vector<int>& trustedBy = new int[n + 1];
        foreach (var t in trust) {
            trustCount[t[0]]++;
            trustedBy[t[1]]++;
        }
        for (int i = 1; i <= n; i++) {
            if (trustCount[i] == 0 && trustedBy[i] == n - 1) {
                return i;
            }
        }
        return -1;
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int FindJudge(int n, int[][] trust) {
        if (trust.length == 0 && n == 1) {
            return 1;
        }
        int[] trustCount = new int[n + 1];
        int[] trustedBy = new int[n + 1];
        foreach (var t in trust) {
            trustCount[t[0]]++;
            trustedBy[t[1]]++;
        }
        for (int i = 1; i <= n; i++) {
            if (trustCount[i] == 0 && trustedBy[i] == n - 1) {
                return i;
            }
        }
        return -1;
    }
}

JavaScript solution

matched/original

class Solution {
    findJudge(n, trust) {
        if (trust.length === 0 && n === 1) return 1;

        const trustCount = new Array(n + 1).fill(0);
        const trustedBy = new Array(n + 1).fill(0);

        for (const [a, b] of trust) {
            trustCount[a]++;
            trustedBy[b]++;
        }

        for (let i = 1; i <= n; i++) {
            if (trustCount[i] === 0 && trustedBy[i] === n - 1) {
                return i;
            }
        }

        return -1;
    }
}

Python solution

matched/original

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        if not trust and n == 1:
            return 1

        trust_count = [0] * (n + 1)
        trusted_by = [0] * (n + 1)

        for a, b in trust:
            trust_count[a] += 1
            trusted_by[b] += 1

        for i in range(1, n + 1):
            if trust_count[i] == 0 and trusted_by[i] == n - 1:
                return i

        return -1

Explanation

Algorithm

1⃣Создание счетчиков доверия:

Инициализируйте массив для подсчета количества людей, которым доверяет каждый человек, и массив для подсчета количества людей, которые доверяют каждому человеку.

2⃣Подсчет доверия:

Пройдитесь по каждому элементу в массиве trust и обновите счетчики: увеличьте количество доверий для того, кто доверяет, и увеличьте количество доверенных людей для того, кому доверяют.

3⃣Проверка условий судьи:

Пройдитесь по массиву людей и найдите того, кто никому не доверяет (количество доверий равно 0) и кому доверяют все остальные (количество доверенных людей равно n-1). Верните метку этого человека. Если такого человека нет, верните -1.

😎