Go/C語(yǔ)言LeetCode題解997找到小鎮(zhèn)法官

更新時(shí)間：2022年12月28日 11:10:49 作者：劉09k11

這篇文章主要為大家介紹了Go語(yǔ)言LeetCode題解997找到小鎮(zhèn)的法官示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目描述

997. 找到小鎮(zhèn)的法官 - 力扣（LeetCode）

小鎮(zhèn)里有 n 個(gè)人，按從 1 到 n 的順序編號(hào)。傳言稱，這些人中有一個(gè)暗地里是小鎮(zhèn)法官。

如果小鎮(zhèn)法官真的存在，那么：

小鎮(zhèn)法官不會(huì)信任任何人。
每個(gè)人（除了小鎮(zhèn)法官）都信任這位小鎮(zhèn)法官。
只有一個(gè)人同時(shí)滿足屬性 1 和屬性 2 。

給你一個(gè)數(shù)組 trust ，其中 trust[i] = [ai, bi] 表示編號(hào)為 ai 的人信任編號(hào)為 bi 的人。

如果小鎮(zhèn)法官存在并且可以確定他的身份，請(qǐng)返回該法官的編號(hào)；否則，返回 -1 。

示例 1：

輸入：n = 2, trust = [[1,2]]
輸出：2

示例 2：

輸入：n = 3, trust = [[1,3],[2,3]]
輸出：3

示例 3：

輸入：n = 3, trust = [[1,3],[2,3],[3,1]]
輸出：-1

提示：

1 <= n <= 1000

0 <= trust.length <= 10^4

trust[i].length == 2[=

trust 中的所有trust[i] = [ai, bi] 互不相同

ai != bi

1 <= ai, bi <= n

思路分析

記錄每個(gè)人被信任的次數(shù)。信任次數(shù)為n-1的人就是法官

同時(shí)如果這個(gè)人信任別過(guò)人就讓他的被信任次數(shù)-1 (這個(gè)操作主要是判斷一個(gè)人不是法官，如果一個(gè)人被其他人信任了n-1次，那么這個(gè)人可能是法官，如果這個(gè)人信任過(guò)別人，那么讓他的被信任次數(shù)-1，他的被信任次數(shù)為n-2!=n-1。這樣就滿足了法官不能信別人的邏輯，他也就不是法官。)

有人被信任的次數(shù)為n-1,那么他就是法官！沒(méi)有這樣的人，那么返回-1.

go 代碼

class Solution {
    public static int findJudge(int n, int[][] trust) {
        int[] times=new int[n+1];
        for(int i=0;i&lt;trust.length;i++){
            times[trust[i][1]]++;
            times[trust[i][0]]--;
        }
        for(int i=1;i&lt;=n;i++){
            if(times[i]==n-1) return i;
        }
        return -1;
    }
}

C語(yǔ)言

暴力法

關(guān)鍵點(diǎn)：

1：關(guān)鍵點(diǎn)兩個(gè)，一個(gè)是相信的人數(shù)，一個(gè)是不能相信人

2：用hashSet去記錄，如果相信別人，那么這個(gè)人的信用設(shè)置為負(fù)數(shù)。

3：被相信的人，hashSet信用值增加

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(n)

代碼

int findJudge(int n, int** trust, int trustSize, int* trustColSize)
{
    //根據(jù)入度進(jìn)行遍歷
    int hashSet[n+1]; //相信這個(gè)i的人數(shù)
    memset(hashSet,0, sizeof(hashSet));
    for(int i = 0; i < trustSize; i++)
    {
        hashSet[trust[i][1]]++;
        //相信別人 就不能是法官
        hashSet[trust[i][0]] = INT_MIN;
        
    }
      for(int i = 1; i <= n; i++)
    {
        if(hashSet[i] == n-1 )
        {
            return i;
        }
    }
          return -1;
}

參考

一題兩解：哈希表 & 優(yōu)化！ - 找到小鎮(zhèn)的法官 - 力扣（LeetCode）

以上就是Go/C語(yǔ)言LeetCode題解997找到小鎮(zhèn)法官的詳細(xì)內(nèi)容，更多關(guān)于Go/C語(yǔ)言題解找到小鎮(zhèn)法官的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: