leetcode997找到小镇的法官
思路
- 蠢方法,维护一个二维数组,横全为0,竖除了自己全是1。
厉害的方法,出度和度之差为n-1,相信入度为n-1,不相信任何人为0。而且这样的人只有一个。
include
include
//leetcode直接用trust[][]
int findJudge(int n, int* trust, int trustSize, int trustColSize){int flag[n+1][n+1],res=0;
memset(flag,0,(n+1)*(n+1)*sizeof(int));
int i,j,l=0,h=0;
for(i=0;i<trustSize;i++){
h = *((int*)trust+i*(*trustColSize)+0);
l = *((int*)trust+i*(*trustColSize)+1);
flag[h][l] = 1;
}
for(i=1;i<=n;i++){
res = i;
for(j=1;j<=n;j++){
if(i!=j){
if(flag[i][j]==1){
res = 0;
break;
}
}
}
if(res!=0)
break;
}
if (res==0)
{
return -1;
}
for(i=1;i<=n;i++){
if(i!=res){
if(flag[i][res]==0){
res =0;
break;
}
}
}
if(res==0)
return -1;
else
return res;
}
int main(){
int trust[3][2] = { { 1,3},{ 2,3},{ 3,1}};
int trust1[5][2] = { { 1,3},{ 1,4},{ 2,3},{ 2,4},{ 4,3}};
int len = 2;
int *p = &len;
int res = findJudge(4,(int **)trust1,5,p);
printf("res = %d\n",res);
}
聪明办法
#include<stdio.h>
#include<string.h>
//leetcode直接用trust[][]
int findJudge(int n, int** trust, int trustSize, int* trustColSize){
int flag[n+1];
memset(flag,0,(n+1)*sizeof(int));
int i,l,h;
for(i=0;i<trustSize;i++){
l=*((int*)trust+i*(*trustColSize)+0);
h=*((int*)trust+i*(*trustColSize)+1);
flag[h]++;
flag[l]--;
}
int res=0,res1=0;
for(i=1;i<=n;i++){
if(flag[i]==n-1){
return i;
}
}
return -1;
}
int main(){
int trust[3][2] = { { 1,3},{ 2,3},{ 3,1}};
int trust1[5][2] = { { 1,3},{ 1,4},{ 2,3},{ 2,4},{ 4,3}};
int len = 2;
int *p = &len;
int res = findJudge(3,(int **)trust,3,p);
printf("res = %d\n",res);
}
还没有评论,来说两句吧...