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:
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</code"><!--=-->0 <= trust.length <="104</code"><!--=-->trust[i].length == 2-
All the pairs of
trustare unique. -
ai != bi 1 <= ai, bi <="n</code"><!--=-->
就是给了一个长度为n的数组的数组[a, b]，表示a信任b，要找出唯一一个人，他不信任任何人，且其他所有人都信任他。其实看完题就想到了graph，但已经把graph全忘光了，于是就自己哼哧哼哧写了个brute force解法。
my brute force solution:
先把所有人放到一个set里，把出现在第一个的人remove掉，最后如果剩且只剩下一个人，这个人就是possible judge，否则return -1。然后再看一遍其他所有人是不是都trust这个possible judge。
class Solution {
public int findJudge(int n, int[][] trust) {
Set<integer> set = new HashSet<>();
for (int i = 1; i <= n; i++) { set.add(i); } for (int[] i : trust) set.remove(i[0]); if (set.size() !="1)" return -1; iterator<integer> it = set.iterator();
int judge = it.next();
int[] all = new int[n + 1];
all[0] = 1;
all[judge] = 1;
for (int[] i : trust) {
if (i[1] == judge) {
all[i[0]] = 1;
}
}
for (int i : all) {
if (i == 0) {
return -1;
}
}
return judge;
}
}</=></integer>
然后看了解答，虽然是用的graph的思想但其实挺简单的，相当于judge的in degree是n -1，out degree是0，所以in – out = n -1。怎么保证没有其他的情况这个我还没想明白。如果分开计算in degree和out degree的话需要两个数组，但计算差值只需要一个数组。in degree（作为b）时++，out degree（作为a）时–。
class Solution {
public int findJudge(int n, int[][] trust) {
int[] all = new int[n + 1];
for (int[] i : trust) {
all[i[0]]--;
all[i[1]]++;
}
for (int i = 1; i < n + 1; i++) {
if (all[i] == n - 1) {
return i;
}
}
return -1;
}
}
Original: https://blog.csdn.net/qq_37333947/article/details/128330372
Author: wenyq7
Title: LeetCode 997. Find the Town Judge
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/722098/
转载文章受原作者版权保护。转载请注明原作者出处！