LeetCode #997 Find the Town Judge 找到小鎮(zhèn)的法官

997 Find the Town Judge 找到小鎮(zhèn)的法官

Description:
In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

The town judge trusts nobody.
Everybody (except for the town judge) trusts the town judge.
There is exactly one person that satisfies properties 1 and 2.
You are given trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b.

If the town judge exists and can be identified, return the label of the town judge. Otherwise, return -1.

Example:

Example 1:

Input: N = 2, trust = [[1,2]]
Output: 2

Example 2:

Input: N = 3, trust = [[1,3],[2,3]]
Output: 3

Example 3:

Input: N = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

Example 4:

Input: N = 3, trust = [[1,2],[2,3]]
Output: -1
Example 5:

Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
Output: 3

Note:

1 <= N <= 1000
trust.length <= 10000
trust[i] are all different
trust[i][0] != trust[i][1]
1 <= trust[i][0], trust[i][1] <= N

題目描述:
在一個(gè)小鎮(zhèn)里糊啡,按從 1 到 N 標(biāo)記了 N 個(gè)人。傳言稱炫刷,這些人中有一個(gè)是小鎮(zhèn)上的秘密法官。

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

小鎮(zhèn)的法官不相信任何人雪侥。
每個(gè)人(除了小鎮(zhèn)法官外)都信任小鎮(zhèn)的法官彰亥。
只有一個(gè)人同時(shí)滿足屬性 1 和屬性 2 葱色。
給定數(shù)組 trust卸伞,該數(shù)組由信任對 trust[i] = [a, b] 組成抹镊,表示標(biāo)記為 a 的人信任標(biāo)記為 b 的人。

如果小鎮(zhèn)存在秘密法官并且可以確定他的身份瞪慧,請返回該法官的標(biā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

示例 4:

輸入:N = 3, trust = [[1,2],[2,3]]
輸出:-1

示例 5:

輸入:N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
輸出:3

提示:

1 <= N <= 1000
trust.length <= 10000
trust[i] 是完全不同的
trust[i][0] != trust[i][1]
1 <= trust[i][0], trust[i][1] <= N

思路:

遍歷 trust數(shù)組, 記錄出度和入度的差, 返回出度和入度差為 N - 1的人
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(n)

代碼:
C++:

class Solution 
{
public:
    int findJudge(int N, vector<vector<int>>& trust) 
    {
        vector<int> count(N, 0);
        for (const auto& person : trust) 
        {
            --count[person[0] - 1];
            ++count[person[1] - 1];
        }
        for (int i = 0; i < N; i++) if (count[i] == N - 1) return i + 1;
        return -1;
    }
};

Java:

class Solution {
    public int findJudge(int N, int[][] trust) {
        int count[] = new int[N];
        for (int[] person : trust) {
            count[person[0] - 1]--;
            count[person[1] - 1]++;
        }
        for (int i = 0; i < N; i++) if (count[i] == N - 1) return i + 1;
        return -1;
    }
}

Python:

class Solution:
    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        count = [0] * N
        for person in trust:
            count[person[0] - 1] -= 1
            count[person[1] - 1] += 1
        for i, person in enumerate(count):
            if person == N - 1:
                return i + 1
        return -1
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市儡炼,隨后出現(xiàn)的幾起案子妓湘,更是在濱河造成了極大的恐慌,老刑警劉巖乌询,帶你破解...
    沈念sama閱讀 217,542評論 6 504
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件榜贴,死亡現(xiàn)場離奇詭異,居然都是意外死亡妹田,警方通過查閱死者的電腦和手機(jī)唬党,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,822評論 3 394
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來鬼佣,“玉大人驶拱,你說我怎么就攤上這事【е裕” “怎么了蓝纲?”我有些...
    開封第一講書人閱讀 163,912評論 0 354
  • 文/不壞的土叔 我叫張陵冲泥,是天一觀的道長呐赡。 經(jīng)常有香客問我榆骚,道長臀玄,這世上最難降的妖魔是什么钧舌? 我笑而不...
    開封第一講書人閱讀 58,449評論 1 293
  • 正文 為了忘掉前任董饰,我火速辦了婚禮旁壮,結(jié)果婚禮上偶宫,老公的妹妹穿的比我還像新娘哥牍。我一直安慰自己露懒,他們只是感情好闯冷,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,500評論 6 392
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著懈词,像睡著了一般蛇耀。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上坎弯,一...
    開封第一講書人閱讀 51,370評論 1 302
  • 那天纺涤,我揣著相機(jī)與錄音,去河邊找鬼抠忘。 笑死撩炊,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的崎脉。 我是一名探鬼主播拧咳,決...
    沈念sama閱讀 40,193評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼囚灼!你這毒婦竟也來了骆膝?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 39,074評論 0 276
  • 序言:老撾萬榮一對情侶失蹤灶体,失蹤者是張志新(化名)和其女友劉穎阅签,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體蝎抽,經(jīng)...
    沈念sama閱讀 45,505評論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡政钟,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,722評論 3 335
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了樟结。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片养交。...
    茶點(diǎn)故事閱讀 39,841評論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖瓢宦,靈堂內(nèi)的尸體忽然破棺而出层坠,到底是詐尸還是另有隱情,我是刑警寧澤刁笙,帶...
    沈念sama閱讀 35,569評論 5 345
  • 正文 年R本政府宣布破花,位于F島的核電站,受9級特大地震影響疲吸,放射性物質(zhì)發(fā)生泄漏座每。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,168評論 3 328
  • 文/蒙蒙 一摘悴、第九天 我趴在偏房一處隱蔽的房頂上張望峭梳。 院中可真熱鬧,春花似錦、人聲如沸葱椭。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,783評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽孵运。三九已至秦陋,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間治笨,已是汗流浹背驳概。 一陣腳步聲響...
    開封第一講書人閱讀 32,918評論 1 269
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留旷赖,地道東北人顺又。 一個(gè)月前我還...
    沈念sama閱讀 47,962評論 2 370
  • 正文 我出身青樓,卻偏偏與公主長得像等孵,于是被迫代替她去往敵國和親稚照。 傳聞我的和親對象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,781評論 2 354

推薦閱讀更多精彩內(nèi)容