LeetCode #997 Find the Town Judge 找到鎮上的法官

英文原文如下

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] = [a_i, b_i] representing that the person labeled a_i trusts the person labeled b_i. If a trust relationship does not exist in trust array, then such a trust relationship does not exist.

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

中文翻譯

在一座鎮上，有 n 個人並被編號從 1 到 n 。 在這裡有一個傳言就是這些人之中有一個其實祕密地擔任鎮上的法官。

如果城鎮的法官存在，則滿足以下條件

1. 鎮上的法官不相信任何人
2. 所有人(除了法官)都相信著法官
3. 恰好有一個人滿足上述1跟2的屬性

給予你一個陣列 trust ，陣列中的任一元素都包含了兩個編號 trust[i] = [a_i, b_i] ，代表了編號 a_i 的人相信編號 b_i 的人。

要是 trust  陣列中沒有出現信賴的關係，則該信賴關係不存在。

要是鎮上的法官存在並可以被認出，回傳他的編號，否則回傳 -1

範例及題目限制

解題思路

在這一題中，我們使用了HashSet以及Dictionary來解決

分別儲存了， HashSet : 信任過其它人的人他們的編號 (用來找出法官是否存在)

Dictionary : key是編號，value則是其被別人信任的次數

C# 解決方案

方案1

public class Solution {
    public int FindJudge(int n, int[][] trust) {
        // If there is only one person in the town, that person must be the judge.
        if(n==1){
            return 1;
        }

        HashSet<int> hSet = new HashSet<int>();    //store the people who trust another one.
        Dictionary<int,int> dict =  new Dictionary<int,int>();  //store the count of trusts for each person.

        foreach(var item in trust){
            hSet.Add(item[0]);
            if (!dict.ContainsKey(item[1]))
            {
                dict.Add(item[1], 1);
            }
            else
            {
                dict[item[1]] = dict[item[1]]+1;
            }
        }

        //除了法官之外，所有人都相信法官，所以要是法官存在則HashSet的Count會是 n-1
        if(hSet.Count!=n-1){    
            return -1;
        }

        // 用LINQ找到被所有人(除了自己)相信著的人，要是存在，則他就是法官
        int key = dict.FirstOrDefault(x => x.Value == n-1).Key;
        return key>0 ? key : -1;
    }
}

結論

這一題挺有趣的，就像是個解謎挑戰呢!

話說寫這篇文章的時候是元宵節，湯圓好好吃~

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡收藏文章或幫我點個廣告，那都是對我的支持

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Find the Town Judge – LeetCode

一些隨機的LeetCode文章