leetcode997找到小镇的法官

傷城~ 2022-08-29 00:26 113阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]  
思路

1.  蠢方法，维护一个二维数组，横全为0，竖除了自己全是1。
2.  **厉害的方法**，出度和度之差为n-1，相信入度为n-1，不相信任何人为0。而且这样的人只有一个。

#include<stdio.h>
    #include<string.h>
    //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);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20220829/be22a3aea3b64e7d8dc304bc64d23a5a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]: /images/20220829/33d55dc6ca5b4cbea7d3210943600588.png