Go/C語言LeetCode題解997找到小鎮(zhèn)法官
題目描述
997. 找到小鎮(zhèn)的法官 - 力扣(LeetCode)
小鎮(zhèn)里有 n
個人,按從 1
到 n
的順序編號。傳言稱,這些人中有一個暗地里是小鎮(zhèn)法官。
如果小鎮(zhèn)法官真的存在,那么:
- 小鎮(zhèn)法官不會信任任何人。
- 每個人(除了小鎮(zhèn)法官)都信任這位小鎮(zhèn)法官。
- 只有一個人同時滿足屬性 1 和屬性 2 。
給你一個數(shù)組 trust
,其中 trust[i] = [ai, bi]
表示編號為 ai
的人信任編號為 bi
的人。
如果小鎮(zhèn)法官存在并且可以確定他的身份,請返回該法官的編號;否則,返回 -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
思路分析
記錄每個人被信任的次數(shù)。 信任次數(shù)為n-1的人就是法官
同時如果這個人信任別過人就讓他的被信任次數(shù)-1 (這個操作主要是判斷一個人不是法官,如果一個人被其他人信任了n-1次,那么這個人可能是法官,如果這個人信任過別人,那么讓他的被信任次數(shù)-1,他的被信任次數(shù)為n-2!=n-1。這樣就滿足了法官不能信別人的邏輯,他也就不是法官。)
有人被信任的次數(shù)為n-1,那么他就是法官!沒有這樣的人,那么返回-1.
go 代碼
class Solution { public static int findJudge(int n, int[][] trust) { int[] times=new int[n+1]; for(int i=0;i<trust.length;i++){ times[trust[i][1]]++; times[trust[i][0]]--; } for(int i=1;i<=n;i++){ if(times[i]==n-1) return i; } return -1; } }
C語言
暴力法
關(guān)鍵點(diǎn):
1:關(guān)鍵點(diǎn)兩個,一個是相信的人數(shù),一個是不能相信人
2:用hashSet去記錄,如果相信別人,那么這個人的信用設(shè)置為負(fù)數(shù)。
3:被相信的人,hashSet信用值增加
時間復(fù)雜度:O(n)
空間復(fù)雜度:O(n)
代碼
int findJudge(int n, int** trust, int trustSize, int* trustColSize) { //根據(jù)入度進(jìn)行遍歷 int hashSet[n+1]; //相信這個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語言LeetCode題解997找到小鎮(zhèn)法官的詳細(xì)內(nèi)容,更多關(guān)于Go/C語言題解找到小鎮(zhèn)法官的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
Ruby序列化和持久化存儲(Marshal、Pstore)操作方法詳解
這篇文章主要介紹了Ruby序列化和持久化存儲(Marshal、Pstore)操作方法詳解,包括Ruby Marshal序列化,Ruby Pstore存儲,需要的朋友可以參考下2022-04-04golang協(xié)程關(guān)閉踩坑實戰(zhàn)記錄
協(xié)程(coroutine)是Go語言中的輕量級線程實現(xiàn),下面這篇文章主要給大家介紹了關(guān)于golang協(xié)程關(guān)閉踩坑的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-03-03Go語言設(shè)計實現(xiàn)在任務(wù)欄里提醒你喝水的兔子
這篇文章主要為大家介紹了Go語言設(shè)計實現(xiàn)在任務(wù)欄里提醒你喝水的兔子示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-01-01使用Gin框架返回JSON、XML和HTML數(shù)據(jù)
Gin是一個高性能的Go語言Web框架,它不僅提供了簡潔的API,還支持快速的路由和中間件處理,在Web開發(fā)中,返回JSON、XML和HTML數(shù)據(jù)是非常常見的需求,本文將介紹如何使用Gin框架來返回這三種類型的數(shù)據(jù),需要的朋友可以參考下2024-08-08