LeeCode-刷题日记-Day32

997. 找到小镇的法官

思路：出度与入度。

/**
 * @param {number} n
 * @param {number[][]} trust
 * @return {number}
 */
var findJudge = function(n, trust) {
    const inDegrees=new Array(n+1).fill(0)
    const outDegrees=new Array(n+1).fill(0)
    for(let num of trust){
        let x=num[0],y=num[1];
        ++inDegrees[y];
        ++outDegrees[x];
    }
    for(let i=1;i<n+1;++i){
        if(outDegrees[i]===0&&inDegrees[i]===n-1){
            return i;
        }
    }
    return -1;
};

1557. 可以到达所有点的最少点数目

思路：一个节点无法到达，那么意味着他的入度为0。即关注节点的入度，寻找入度为0的节点加入结果集中。

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[]}
 */
var findSmallestSetOfVertices = function(n, edges) {
    let flag = new Array(n).fill(0);
    for(let [from,to] of edges){
        flag[to]=1;
    }
    let res=[]
    for(let i=0;i<n;i++){
        if(flag[i]===0){
            res.push(i);
        }
    }
    return res;
};

841. 钥匙和房间

思路：创建一个队列。每次将访问到的房间内所有节点加入队列。再将此房间至为false防止重复访问。从队列中拿出所有节点，访问到房间再加入队列。每次访问一个房间即房间数加1。最终判断是否进入所有房间即可。

/**
 * @param {number[][]} rooms
 * @return {boolean}
 */
var canVisitAllRooms = function(rooms) {
    let pass = rooms[0],index=1;
    rooms[0]=false;
    while(pass.length>0){
        let arr = pass.splice(0,pass.length);
        for(let item of arr){
            if(rooms[item]!==false){
                pass.push(...rooms[item].splice(0,rooms[item].length))
                index++;
                rooms[item]=false;
            }
        }
    }
    return index===rooms.length;
};