Q997FindTheTownJudge
簡介
小鎮里有 n 個人，按從 1 到 n 的順序編號，傳言稱，這些人中有一個暗地里是小鎮法官，
如果小鎮法官真的存在，那么：
小鎮法官不會信任任何人，
每個人（除了小鎮法官）都信任這位小鎮法官，
只有一個人同時滿足屬性 1 和屬性 2 ，
給你一個陣列 trust ，其中 trust[i] = [ai, bi] 表示編號為 ai 的人信任編號為 bi 的人，
如果小鎮法官存在并且可以確定他的身份，請回傳該法官的編號；否則，回傳 -1 ，
示例 1：
輸入：n = 2, trust = [ [1, 2] ]
輸出：2
示例 2：
輸入：n = 3, trust = [ [1, 3], [2, 3] ]
輸出：3
示例 3：
輸入：n = 3, trust = [ [1, 3], [2, 3], [3, 1] ]
輸出：-1
https://leetcode.cn/problems/find-the-town-judge
解題思路
通過圖的入度和出度來解題，根據題意，a信任b，則a的出度增加1，b的入度增加1，這樣只有當一個人滿足出度為0（不信任任何人），入度為n-1（除法官都信任法官）的時候，這個人就是法官，
代碼
public class Q997FindTheTownJudge {
public int findJudge(int n, int[][] trust) {
int[] inEdges = new int[n+1];
int[] outEdges = new int[n+1];
for (int[] ints : trust) {
outEdges[ints[0]]++;
inEdges[ints[1]]++;
}
for (int i = 1; i < n+1; i++) {
if (inEdges[i] == n-1 && outEdges[i] == 0){
return i;
}
}
return -1;
}
}
測驗
public class Q997FindTheTownJudgeTest {
private Q997FindTheTownJudge q = new Q997FindTheTownJudge();
@Test
public void test1() {
assertEquals(2, q.findJudge(2, new int[][]{{1,2}}));
}
@Test
public void test2() {
assertEquals(3, q.findJudge(3, new int[][]{{1,3},{2,3}}));
}
@Test
public void test3() {
assertEquals(-1, q.findJudge(3, new int[][]{{1,3},{2,3},{3,1}}));
}
}
提交結果
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/501732.html
標籤：其他
上一篇：HCNP Routing&Switching之PKI公鑰基礎架構
下一篇：漫談測驗成長之探索——測驗檔案