leetcode997：找到小镇的法官 #65

Activity

1. sisterAn

   added

   LeetCode

   on Jun 15, 2020
2. sisterAn commented on Jun 15, 2020

   

   sisterAn

   on Jun 15, 2020

   Last edited by sisterAn

   OwnerAuthor

   More actions

   解答：利用图

   本题是一道典型的有向图问题，不理解图的可以看这篇：初学者应该了解的数据结构 Graph，寻找法官即是寻找 入度为N-1，出度为0的点

   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 
     })
   };

   时间复杂度：O(N)

   空间复杂度：O(N)

   另一种解法：

   其实法官也是唯一一个 出入度差值为 N-1 ，所以这里可以简化为寻找出入度差值为 N-1

   let findJudge = function(N, trust) {
     let graph = Array(N+1).fill(0)
     // 出度加一
     // 入度减一
     trust.forEach(([a, b]) => {
       graph[a]--
       graph[b]++
     })
     return graph.findIndex((node, index) => {
       // 剔除0
       return index != 0 && node === N-1 
     })
   };

   时间复杂度：O(N)

   空间复杂度：O(N)

   leetcode
3. 7777sea commented on Jun 16, 2020

   

   7777sea

   on Jun 16, 2020

   Last edited by sisterAn

   More actions

   

   /**
    * @param {number} N
    * @param {number[][]} trust
    * @return {number}
    */
   var findJudge = function(N, trust) {
       
       let inDegree = new Array(N).fill(0);
       let outDegree = new Array(N).fill(0);
   
       trust.forEach((_, index) => {
           inDegree[_[1] - 1]++;
           outDegree[_[0] - 1]++;
       })
       
       for(let i=0; i<N; i++){
           if(inDegree[i] == (N-1) && outDegree[i] == 0){
               return i + 1
           }
       }
   
       return -1
   };
4. zhaozhaopeng68 commented on Jun 16, 2020

   

   zhaozhaopeng68

   on Jun 16, 2020

   Last edited by sisterAn

   More actions

   function getTrust(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
   }

   👍React with 👍1Reacted by 行书子
5. huangruitian commented on Jun 16, 2020

   

   huangruitian

   on Jun 16, 2020

   More actions

   1. 代码比较简洁的写法

   var findJudge = function(N, trust) {
     //很明显是图的问题，求出度为0，入度为N-1的那个节点，即法官
     //构造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 
     })
   };

   2. 其实我们不用计算出入度

   var findJudge = function(N, trust) {
     //事实上我们真的有必要去算每个节点的出度入度嘛？
     //其实是不用的，我们只需要算出度和入度的差值是N-1即可
     //也就是说入度加1,出度减1；
     let graph = Array(N+1).fill(0)
     trust.forEach(([a, b]) => {
       graph[a]--
       graph[b]++
     })
     return graph.findIndex((node, index) => {
       return index != 0 && node == N-1 
     })
   };

   👍React with 👍1Reacted by 瓶子君
6. syc666 commented on Jun 17, 2020

   

   syc666

   on Jun 17, 2020

   More actions

   const fun = (N, trust) => {
       if(N===1) return 1
       const newTrust = []
       trust.forEach(([x,y])=>{
           newTrust[x] = -1
           newTrust[y] = newTrust[y] === undefined ? 1 : newTrust[y] ? ++newTrust[y] : -1
       })
       return newTrust.findIndex(val=>val===N-1)
   }
7. zo11o commented on Dec 18, 2020

   

   zo11o

   on Dec 18, 2020

   Last edited by zo11o

   More actions

   比较挫，就是很好理解
   /**
    * @param {number} N
    * @param {number[][]} trust
    * @return {number}
    */
   var findJudge = function (N, trust) {
       var ac = new Array(N).fill(1);
       // 通过所有标号构建一个数组
       var peoples = ac.map((o, i) => o + i)
       var map = {}
   
       if (N == 1 && !trust.length) {
           return [1]
       }
   
       for (let i = 0; i < trust.length; i++) {
           let idx = peoples.indexOf(trust[i][0])
           //  由于法官没有信任的人，那就数组中移除有信任人的元素
           if (idx !== -1) {
               peoples.splice(idx, 1)
           }
           if (map[trust[i][1]] != null) {
               map[trust[i][1]] = map[trust[i][1]] + 1
           } else {
               map[trust[i][1]] = 1
           }
       }
   
       for (let i = 0; i < peoples.length; i++) {
           if (map[peoples[i]] === N - 1) {
               return peoples[i]
           }
       }
   
       return -1
   };