窩不知道
0%

Leetcode - 997 with Python and Golang

發表於 更新於 分類於 ， ， ， Disqus：

前言

紀錄一下解決 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:

The town judge trusts nobody.
Everybody (except for the town judge) trusts the town judge.
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. 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 otherwise.

Example 1:

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

Example 2:

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

Example 3:

1
2
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

題目要求我們要找出城鎮法官，而這座城鎮的人都相信法官，但法官不信任任何人
基於這個條件來找出法官
n 是總人數
trust[0] 相信 trust[1]

解題過程

一開始覺得這題簡單到爆炸，想說只要有相信人(出現在trust[0])，那個人就一定不是法官
所以想出這個方式

Wrong Answer

1
2
3
4
5
6
7
8
9
10
11
"""
Wrong Answer
"""
class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        all_people = {i: None for i in range(1, n+1)}
        for path in trust:
            all_people.pop(path[1], None)
        for k in all_people.keys():
            return k
        return -1

但這個解答沒有考慮到法官必須要被每個人相信(思考不夠周全)
所以我們必須要知道更詳細的資料

根據上面的 code 我們稍微修改一下
將 all_people 的 value 改為 0
0: 多少個人信任這個人 (法官必須被所有人信任)
然後只要出現在 trust[0] 的都可以刪掉 (法官不信任任何人)

使用Python

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        all_people = {i: 0 for i in range(1, n+1)}
        for i in trust:
            all_people.pop(i[0], None)
            try:
                all_people[i[1]] += 1
            except KeyError:
                pass
        for k, v in all_people.items():
            if v == n - 1:
                return k
        return -1

使用 Golang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func findJudge(n int, trust [][]int) int {
    TrustCounter := map[int]int{}
    result := -1
    // Make map
    for i := 1; i <= n; i++{
        TrustCounter[i] = 0
    }
    for _, v := range trust {
        delete(TrustCounter, v[0])
        if _, ok := TrustCounter[v[1]]; ok {
            TrustCounter[v[1]] += 1
        }
    }
    for k, v := range TrustCounter{
        if v == n - 1 {
            result = k
        }
    }
    return result
}

使用 Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    func findJudge(_ n: Int, _ trust: [[Int]]) -> Int {
        var trustCount: [Int: Int] = [:]
        for i in 1...n {
            trustCount[i] = 0
        }
        for i in trust {
            trustCount.removeValue(forKey: i[0])
            var beTrusted = trustCount[i[1]]
            if beTrusted != nil {
                trustCount[i[1]] = beTrusted! + 1
            }
        }
        for (k, v) in trustCount{
            if v == n - 1 {
                return k
            }
        }
        return -1
    }
}

另一種方法

我們可以用 list (golang: slice) 來完成
首先宣告一個 list(假設叫 trustCount)，長度為 n + 1
再來遍歷trust
第一個人的 trustCount 必須 -1 (法官不能相信任何人，所以要減，讓後面條件不會過)
第二個人的 trustCount 必須 +1
最後遍歷trustCount

使用Python

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        trust_count = [0] * (n + 1)
        for a, b in trust:
            trust_count[a] -= 1
            trust_count[b] += 1
        for i in range(1, n + 1):
            if trust_count[i] == n - 1:
                return i
        return -1

使用Golang

1
2
3
4
5
6
7
8
9
10
11
12
13
func findJudge(n int, trust [][]int) int {
    trustCount := make([]int, n+1)
    for _, t := range trust {
        trustCount[t[0]]--
        trustCount[t[1]]++
    }
    for i := 1; i <= N; i++ {
        if trustCount[i] == n - 1 {
            return i
        }
    }
    return -1
}

使用Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    func findJudge(_ n: Int, _ trust: [[Int]]) -> Int {
        var trustCount = Array(repeating: 0, count: n + 1)
        for i in trust {
            trustCount[i[0]] -= 1
            trustCount[i[1]] += 1
        }
        for i in 1...n {
            if trustCount[i] == n - 1 {
                return i
            }
        }
        return -1
    }
}

如果有錯誤的部份，歡迎指正，謝謝。
如果你喜歡這篇文章，請幫我拍手
只需要註冊會員就可以囉，完全不用花費任何一毛錢就可以用來鼓裡創作者囉