Last Updated on 2022-01-03 by Clay
In a town, there aren
people labeled from1
ton
. 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 arraytrust
wheretrust[i] = [ai, bi]
representing that the person labeledai
trusts the person labeledbi
. 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