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
}

最后更新于