997 找到小镇的法官-简单
题目:
小镇里有 n 个人,按从 1 到 n 的顺序编号。传言称,这些人中有一个暗地里是小镇法官。
如果小镇法官真的存在,那么:
小镇法官不会信任任何人。 每个人(除了小镇法官)都信任这位小镇法官。 只有一个人同时满足属性 1 和属性 2 。 给你一个数组 trust ,其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。
如果小镇法官存在并且可以确定他的身份,请返回该法官的编号;否则,返回 -1 。
分享:
直接遍历,信任别人的人直接赋值 -1,被信任的人,如果没有信任别人,直接递增,并保留结果。
最后,判断被信任的人是否得到了所有人的信任。
// date 2023/11/09
func findJudge(n int, trust [][]int) int {
if len(trust) == 0 {
if n == 1 {
return n
}
return -1
}
dp := make([]int , n+1)
dp[0] = -1
res := -1
for _, v := range trust {
dp[v[0]] = -1
if dp[v[1]] != -1 {
dp[v[1]] += 1
res = v[1]
}
}
if dp[res] == n-1 {
return res
}
return -1
}
最后更新于