Open xszi opened 3 years ago
方法一:好理解
function findJudge(N, trust) {
var trustObj = {};
var beTrustObj = {};
trust.forEach(item => {
if(trustObj[item[0]]) {
trustObj[item[0]] = trustObj[item[0]] + 1
} else {
trustObj[item[0]] = 1
}
if(beTrustObj[item[1]]) {
beTrustObj[item[1]] += 1
} else {
beTrustObj[item[1]] = 1
}
})
let has = -1
for(let i = 1; i <= N; i++) {
if(!trustObj[i] && beTrustObj[i] == N - 1) {
has = i
}
}
return has
}
方法二:简洁
let findJudge = function(N, trust) {
//构造0-N个节点的图
let graph = Array.from({length:N+1}, () => ({outDegree:0, inDegree:0}))
trust.forEach(([a, b]) => {
graph[a].outDegree++
graph[b].inDegree++
})
return graph.findIndex(({outDegree, inDegree}, index) => {
//剔除0
return index != 0 && outDegree === 0 && inDegree === N-1
})
};
在一个小镇里,按从 1 到 N 标记了 N 个人。传言称,这些人中有一个是小镇上的秘密法官。
如果小镇的法官真的存在,那么:
如果小镇存在秘密法官并且可以确定他的身份,请返回该法官的标记。否则,返回 -1 。
示例 1:
示例 2:
示例 3:
示例 4:
示例 5:
提示:
1 <= N <= 1000
trust.length <= 10000
trust[i]
是完全不同的trust[i][0] != trust[i][1]
1 <= trust[i][0], trust[i][1] <= N
leetcode