curTain

  1. 找到小镇的法官

997. 找到小镇的法官

在一个小镇里,按从 1 到 N 标记了 N 个人。传言称,这些人中有一个是小镇上的秘密法官。

如果小镇的法官真的存在,那么:

小镇的法官不相信任何人。
每个人(除了小镇法官外)都信任小镇的法官。
只有一个人同时满足属性 1 和属性 2 。
给定数组 trust,该数组由信任对 trust[i] = [a, b] 组成,表示标记为 a 的人信任标记为 b 的人。

如果小镇存在秘密法官并且可以确定他的身份,请返回该法官的标记。否则,返回 -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

解题思路

可知,关系图是图,

图的表示方式有两种:

  1. 邻接矩阵
  2. 邻接表

本题使用邻接表实现

使用对象代替数组实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* @param {number} N
* @param {number[][]} trust
* @return {number}
*/
var findJudge = function(N, trust) {
// 创建邻接表
if( trust.length === 0 && N === 1 ) return 1
let map = {}
for( let item of trust ){
// 存为对象
if( map[ item[0] ] ){
map[ item[0] ].trusting.push( item[1] )
} else {
map[ item[0] ] = {
trusting: [ item[1] ],
trusted: []
}
}
// 将被信任的人也存为对象
if( map[item[1]] ){
map[item[1]].trusted.push( item[0] )
} else {
map[item[1]] = {
trusted: [ item[0] ],
trusting: []
}
}
}

for( let key in map ){
// 信任的人和不信任的人
if( map[key].trusting.length === 0 && map[key].trusted.length === N - 1 ){
return key
}
}
return -1
};

使用数组实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* @param {number} N
* @param {number[][]} trust
* @return {number}
*/
var findJudge = function(N, trust) {
// 创建邻接表
let graph = Array.from({length: N + 1}, () => ({ trusted:[], trusting: []}))
if( trust.length === 0 && N === 1 ) return 1

for( let item of trust ){
graph[item[0]].trusting.push( item[1] )
graph[item[1]].trusted.push( item[0] )
}
for( let i = 0; i < N + 1; i ++ ){
if( graph[i].trusting.length === 0 && graph[i].trusted.length === N - 1 ){
return i
}
}
return -1
};

 评论