Leetcode-997 Find the Town Judge(找到小镇的法官)

作者水平有限，所发仅为个人愚见，如有明显谬误，望斧正

题目可转化为对于所给正整数N（1≤N≤1000），共有N个节点，编号从1-N。其中"相信"这一概念，可看作是一条连接两节点的有向边。如所给二维vector的trust向量数组，trust[i][0]表示有向边的起点，则trust[i][1]表示有向边的终点。所求为满足以下2个条件的节点：①出度(即题目中的属性1)为0 ②入度(即题目中的属性2)为N-1。当且仅当满足以上两个条件的节点数量为1时，所求问题有解，返回节点编号。当满足以上两个条件的节点数量为0或大于1时，所求问题无解，返回值-1。

 

对于输入样例

N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]

有图　　　　　　　　　　　　　　　　　　进而有表

            

 

1 #define pb push_back 2 #define maxSize 3939 3 #define _for(i,a,b) for(int i = (a);i < (b);i ++) 4 5 class Solution 6 { 7 public: 8 int findJudge(int N, vector<vector<int>>& trust) 9 { 10 int hash[N+1][2]; 11 memset(hash,0,sizeof(hash)); 12 13 int sz = trust.size(); 14 _for(i,0,sz) 15 { 16 hash[trust[i][0]][0] ++; 17 hash[trust[i][1]][1] ++; 18 } 19 20 int rnt = -1; 21 _for(i,1,N+1) 22 { 23 if(hash[i][0]==0&&hash[i][1]==N-1) 24 { 25 if(rnt==-1) 26 rnt = i; 27 else 28 return -1; 29 } 30 } 31 return rnt; 32 } 33 }; Leetcode-997(C++)

执行用时:364ms

转载于:https://www.cnblogs.com/Asurudo/p/10427849.html

总结

以上是生活随笔为你收集整理的Leetcode-997 Find the Town Judge(找到小镇的法官)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。