leetcode997找到小镇的法官

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

在这里插入图片描述
在这里插入图片描述
思路

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

    include

    include

    //leetcode直接用trust[][]
    int findJudge(int n, int* trust, int trustSize, int trustColSize){

    1. int flag[n+1][n+1],res=0;
    2. memset(flag,0,(n+1)*(n+1)*sizeof(int));
    3. int i,j,l=0,h=0;
    4. for(i=0;i<trustSize;i++){
    5. h = *((int*)trust+i*(*trustColSize)+0);
    6. l = *((int*)trust+i*(*trustColSize)+1);
    7. flag[h][l] = 1;
    8. }
    9. for(i=1;i<=n;i++){
    10. res = i;
    11. for(j=1;j<=n;j++){
    12. if(i!=j){
    13. if(flag[i][j]==1){
    14. res = 0;
    15. break;
    16. }
    17. }
    18. }
    19. if(res!=0)
    20. break;
    21. }
    22. if (res==0)
    23. {
    24. return -1;
    25. }
    26. for(i=1;i<=n;i++){
    27. if(i!=res){
    28. if(flag[i][res]==0){
    29. res =0;
    30. break;
    31. }
    32. }
    33. }
    34. if(res==0)
    35. return -1;
    36. else
    37. return res;

    }

    int main(){

    1. int trust[3][2] = { { 1,3},{ 2,3},{ 3,1}};
    2. int trust1[5][2] = { { 1,3},{ 1,4},{ 2,3},{ 2,4},{ 4,3}};
    3. int len = 2;
    4. int *p = &len;
    5. int res = findJudge(4,(int **)trust1,5,p);
    6. printf("res = %d\n",res);

    }

聪明办法

  1. #include<stdio.h>
  2. #include<string.h>
  3. //leetcode直接用trust[][]
  4. int findJudge(int n, int** trust, int trustSize, int* trustColSize){
  5. int flag[n+1];
  6. memset(flag,0,(n+1)*sizeof(int));
  7. int i,l,h;
  8. for(i=0;i<trustSize;i++){
  9. l=*((int*)trust+i*(*trustColSize)+0);
  10. h=*((int*)trust+i*(*trustColSize)+1);
  11. flag[h]++;
  12. flag[l]--;
  13. }
  14. int res=0,res1=0;
  15. for(i=1;i<=n;i++){
  16. if(flag[i]==n-1){
  17. return i;
  18. }
  19. }
  20. return -1;
  21. }
  22. int main(){
  23. int trust[3][2] = { { 1,3},{ 2,3},{ 3,1}};
  24. int trust1[5][2] = { { 1,3},{ 1,4},{ 2,3},{ 2,4},{ 4,3}};
  25. int len = 2;
  26. int *p = &len;
  27. int res = findJudge(3,(int **)trust,3,p);
  28. printf("res = %d\n",res);
  29. }

发表评论

表情:
评论列表 (有 0 条评论,205人围观)

还没有评论,来说两句吧...

相关阅读

    相关 ZR#997

    ZR\997 解法: > 找找规律就出来了,全场最简单的一道题。 CODE: include<iostream> include<cstdi...

    相关 997. 找到小镇法官

    在一个小镇里,按从 `1` 到 `N` 标记了 `N` 个人。传言称,这些人中有一个是小镇上的秘密法官。 如果小镇的法官真的存在,那么: 1. 小镇的法官不相信任何人。

    相关 ZROI#997

    [ZROI\997][ZROI_997] 这是某场\\(CF(Div.3)\\)的\\(C\\)题.我当时是选择了现场码. 因为那场\\(CF\\)我没打.这个题我当时