力扣题目——997. 找到小镇的法官

注:本文的代码实现使用的是 JS(JavaScript),为前端中想使用JS练习算法和数据结构的小伙伴提供解题思路。

描述

在一个小镇里,按从 1 到 n 为 n 个人进行编号。传言称,这些人中有一个是小镇上的秘密法官。如果小镇的法官真的存在,那么:

  • 小镇的法官不相信任何人。
  • 每个人(除了小镇法官外)都信任小镇的法官。
  • 只有一个人同时满足条件 1 和条件 2 。

给定数组 trust,该数组由信任对trust[i] = [a, b]组成,表示编号为 a 的人信任编号为 b 的人。

如果小镇存在秘密法官并且可以确定他的身份,请返回该法官的编号。否则,返回 -1。


示例:

输入:n = 2, trust = [[1,2]]
输出:2
输入:n = 3, trust = [[1,3],[2,3]]
输出:3
输入:n = 3, trust = [[1,3],[2,3],[3,1]]
输出:-1
输入:n = 3, trust = [[1,2],[2,3]]
输出:-1
输入:n = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
输出:3

提示:

  • 1 <= n <= 1000
  • 0 <= trust.length <= 104
  • trust[i].length == 2
  • trust[i] 互不相同
  • trust[i][0] != trust[i][1]
  • 1 <= trust[i][0], trust[i][1] <= n

解题思路

直接法

按照体中所给的思路,

  • 小镇的法官不相信任何人:说明trust[i]的第一个元素肯定不能是法官。
  • 任何人(除了法官)都相信法官:说明trust[i]的第一个元素所构成的集合一定包括除了法官的所有人;且若法官存在,则一定在第二个元素所构成的集合中。
  1. 因此,我们可以遍历trust数组,将普通人(除了法官的所有人)都添加到集合people中,把可能是法官的人添加到trusted集合中。
    	let people = new Set()
        let trusted = new Set()
        for(let i = 0, len = trust.length; i < len; i++){
            people.add(trust[i][0])
            trusted.add(trust[i][1])
        }
    
  2. 然后我们需要找到people中没有的人alternative,因为他们很可能是法官
    	let alternative = []
        for(let i = 1; i <= n; i++)
            if(!people.has(i)) alternative.push(i)
    
  3. alternative再和被信赖的人的集合trusted取交集,若交集只有一个元素,说明他基本上就是法官了;若不是一个元素,则一定没有法官
    	let rumors = alternative.filter(item => trusted.has(item))
        if(rumors.length !== 1) return -1
    
  4. 最后检查是否所有人都信任法官,因为第一步中并不能保证所有人都信任法官
    let result = rumors[0]
        for(let i = 1; i <= n; i++){
            if(i !== result ) {
                if(!trust_str.has(i+''+result))
                return -1
            }
        }
    
    完整的代码如下:
    var findJudge = function(n, trust) {
    	// 如果就一个人且他谁也不相信,那他自己就是法官
        if(n === 1 && trust.length === 0) return 1
        let people = new Set()
        let trusted = new Set()
        // 为了最后一步判断是否每个人都相信法官用,所以把trust = [a,b]的形式转为字符串'ab'
        // 能够更好地判断 a 相信 b
        let trust_str = new Set()
        for(let i = 0, len = trust.length; i < len; i++){
            people.add(trust[i][0])
            trusted.add(trust[i][1])
            trust_str.add(trust[i].join(""))
        }
        let alternative = []
        for(let i = 1; i <= n; i++){
            if(!people.has(i)) alternative.push(i)
        }
        let rumors = alternative.filter(item => trusted.has(item))
        if(rumors.length !== 1) return -1
        let result = rumors[0]
        for(let i = 1; i <= n; i++){
            if(i !== result ) {
                if(!trust_str.has(i+''+result))
                return -1
            }
        }
        return result
    };
    
    这种方法纯粹就是根据脑子里的直观感受写出来的,因此算法很简单,按照逻辑写就可以了,期间的一些过程至于为什么,可能需要读者思考一下了。

图论法

我们可以将信任关系看成是一个图,a相信b,则可以认为有个a指向b的箭头。这样,如果有n个人,若b是法官,则有n-1个箭头指向b,且b不会指向任何人。也就是说,法官的入度为n-1出度为0

使用对象存储入度与出度的方法如下:

var findJudge = function(n, trust) {
    if(n === 1 && trust.length === 0) return 1
    let in_obj = {}
    let out_obj = {}
    // 记录每个人的入度和出度
    for(let i = 0, len = trust.length; i< len; i++){
        if(out_obj.hasOwnProperty(trust[i][0])) out_obj[trust[i][0]] ++
        else out_obj[trust[i][0]] = 1
        if(in_obj.hasOwnProperty(trust[i][1])) in_obj[trust[i][1]] ++
        else in_obj[trust[i][1]] = 1
    }
    // 查找入度为 n-1 的人
    let in_set = new Set()
    for(const key in in_obj)
        if(in_obj[key] === n-1) in_set.add(key)
    // 在入度为 n-1 的人中,找出度为0的,也就是在 out_boj 中没出现过的
    for(const item of in_set)
        if(!(item in out_obj) return item
    // 没找到符合要求的
    return -1
};

使用数组存储入度与出度的方法如下:

var findJudge = function(n, trust) {
    let in_list = new Array(n+1).fill(0)
    let out_list = new Array(n+1).fill(0)
    for(const item of trust){
        in_list[item[1]] ++
        out_list[item[0]] ++
    }
    for(let i = 1; i <= n; i++)
        if(in_list[i] === n-1 && out_list[i] === 0)
            return i
    return -1
};
上一篇:contos7 mysql5.7安装


下一篇:CentOS7安装Mysql5.7