Go/C語(yǔ)言LeetCode題解997找到小鎮(zhè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è)人信任別過人就讓他的被信任次數(shù)-1 (這個(gè)操作主要是判斷一個(gè)人不是法官,如果一個(gè)人被其他人信任了n-1次,那么這個(gè)人可能是法官,如果這個(gè)人信任過別人,那么讓他的被信任次數(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語(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)文章!
相關(guān)文章
Ruby序列化和持久化存儲(chǔ)(Marshal、Pstore)操作方法詳解
這篇文章主要介紹了Ruby序列化和持久化存儲(chǔ)(Marshal、Pstore)操作方法詳解,包括Ruby Marshal序列化,Ruby Pstore存儲(chǔ),需要的朋友可以參考下2022-04-04一文掌握Go語(yǔ)言并發(fā)編程必備的Mutex互斥鎖
Go 語(yǔ)言提供了 sync 包,其中包括 Mutex 互斥鎖、RWMutex 讀寫鎖等同步機(jī)制,本篇博客將著重介紹 Mutex 互斥鎖的基本原理,需要的可以參考一下2023-04-04golang協(xié)程關(guān)閉踩坑實(shí)戰(zhàn)記錄
協(xié)程(coroutine)是Go語(yǔ)言中的輕量級(jí)線程實(shí)現(xiàn),下面這篇文章主要給大家介紹了關(guān)于golang協(xié)程關(guān)閉踩坑的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-03-03Go語(yǔ)言設(shè)計(jì)實(shí)現(xiàn)在任務(wù)欄里提醒你喝水的兔子
這篇文章主要為大家介紹了Go語(yǔ)言設(shè)計(jì)實(shí)現(xiàn)在任務(wù)欄里提醒你喝水的兔子示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-01-01使用Gin框架返回JSON、XML和HTML數(shù)據(jù)
Gin是一個(gè)高性能的Go語(yǔ)言Web框架,它不僅提供了簡(jiǎn)潔的API,還支持快速的路由和中間件處理,在Web開發(fā)中,返回JSON、XML和HTML數(shù)據(jù)是非常常見的需求,本文將介紹如何使用Gin框架來返回這三種類型的數(shù)據(jù),需要的朋友可以參考下2024-08-08