LeetCode: 997-Find the Town Judge 解題紀錄

Last Updated on 2022-01-03 by Clay

In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

1. The town judge trusts nobody.
2. Everybody (except for the town judge) trusts the town judge.
3. There is exactly one person that satisfies properties 1 and 2.

You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi.

Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

Example 1:

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

Example 2:

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

Example 3:

Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

Constraints:

• 1 <= n <= 1000
• 0 <= trust.length <= 104
• trust[i].length == 2
• All the pairs of trust are unique.
• ai != bi
• 1 <= ai, bi <= n

我一開始沒有真的看懂這個題目，不過題目的意思其實很單純：一個小鎮上可能存在著一名法官，法官不相信任何人，但每個人都相信著法官。

題目給定的輸入 trust 為一陣列，陣列中的元素格式為 [相信他人的村民編號, 村民相信的人的編號]；而村民的編號從 1 – n（要小心不要習慣性地從 0 開始計算起…）

我們要返回法官的編號，如果不存在法官，則返回 -1。

---

解題思路

本題解題的過程十分單純，那就是計算每個人被信任的次數以及信任他人的次數，如果是法官存在的情況的話，被信任的次數應該是 n-1，信任他人的次數應該是 0。

C++ 範例程式碼

計算信任對象時存在著減去 1 的情況，是因為鎮民的編號是從 1 開始計算，但是列表的索引卻是從 0 開始；反之，最後回傳編號時，是要回傳加上 1 的編號。

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        // Init
        vector<vector<int>> in_out(n, vector<int>(2, 0));
        vector<int> judge({n-1, 0});
        
        // Count
        for (int i=0; i<trust.size(); ++i) {
            ++in_out[trust[i][0]-1][1];
            ++in_out[trust[i][1]-1][0];
        }
        
        // Match
        for (int i=0; i<in_out.size(); ++i) {
            if (in_out[i] == judge) return i+1;
        }
        
        return -1;
    }
};

Python 範例程式碼

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        # Init
        in_out = [[0, 0] for _ in range(n)]
        judge = [n-1, 0]
        
        # Count
        for _in, _out in trust:
            in_out[_in-1][1] += 1
            in_out[_out-1][0] += 1
        
        # Match
        for i in range(len(in_out)):
            if in_out[i] == judge:
                return i+1
        
        return -1

---

References

• https://leetcode.com/problems/find-the-town-judge/

---

Read More

• LeetCode 解題紀錄