Go/C语言LeetCode题解997找到小镇法官

下面是关于“Go/C语言LeetCode题解997找到小镇法官”的完整攻略：

题目描述

在一个小镇里，按从1到N标记了N个人。传言中，这些人中有一个是小镇上的法官。如果小镇的法官真的存在，请你找出他并返回其编号；否则，返回-1。

注意：

1. 要求时间复杂度O(N)，空间复杂度O(1)；
2. 1 <= N <= 1000；
3. trust[i]是一个长度为2的数组，表示信任关系，其中trust[i][0]信任trust[i][1]。

思路分析

首先来理解一下题意，题意中有N个人，其中有一个人是法官。如果这个小镇法官真的存在，那么他满足以下两个条件：

1. 所有其他人都会信任他。
2. 他不信任别人。

使用两个数组分别存储出度和入度，出度表示每个人信任的人数，入度表示每个人被信任的人数。

遍历所有的信任关系，将每个人对其他人的信任统计出来，最后遍历每个人，找到所有出度为0，入度为N-1的人，即为法官。

代码实现

根据上述思路，可以得到以下代码实现：

func findJudge(N int, trust [][]int) int {
    if N == 1 && len(trust) == 0 {
        return 1
    }
    indegrees := make([]int, N+1)
    outdegrees := make([]int, N+1)
    for _, t := range trust {
        outdegrees[t[0]]++
        indegrees[t[1]]++
    }
    for i := 1; i <= N; i++ {
        if indegrees[i] == N-1 && outdegrees[i] == 0 {
            return i
        }
    }
    return -1
}

这是使用Go语言实现的代码，其中包含了对特殊情况的处理（当N为1且信任关系为空时，法官就是这个小镇的唯一居民）。代码先用两个数组记录每个人的出度和入度，再遍历每个人，判断它的出度是否为0，入度是否为N-1，如果符合条件则返回该人的编号，否则返回-1。

以下是使用C语言实现的代码：

int findJudge(int N, int** trust, int trustSize, int* trustColSize){
    int i;
    int *indegrees = calloc(N+1, sizeof(int));
    int *outdegrees = calloc(N+1, sizeof(int));
    for (i = 0; i < trustSize; i++) {
        outdegrees[trust[i][0]]++;
        indegrees[trust[i][1]]++;
    }
    for (i = 1; i <= N; i++) {
        if (indegrees[i] == N-1 && outdegrees[i] == 0) {
            return i;
        }
    }
    return -1;
}

同样是使用了入度和出度这两个数组来记录信任关系，然后遍历每个人，找到符合条件的人返回其编号，否则返回-1。

示例说明

示例一

输入：

• N = 2
• trust = [[1,2]]

输出：

• 2

说明：

• 根据题意，这个小镇只有两个人，1号不可能是法官，所以只能是2号。

示例二

输入：

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

输出：

• 3

说明：

• 1号和2号都没有人信任，不符合法官的第一个条件，只有3号同时满足两个条件，所以是法官。

以上就是完整的“Go/C语言LeetCode题解997找到小镇法官”的攻略了。