leetcode(力扣) 997. 找到小鎮的法官 (劇本殺推理)

文章目錄

• ​​題目描述：​​
• ​​思路分析​​
• ​​完整代碼:​​

題目描述：

小鎮裡有 n 個人，按從 1 到 n 的順序編号。傳言稱，這些人中有一個暗地裡是小鎮法官。

如果小鎮法官真的存在，那麼：

小鎮法官不會信任任何人。

每個人（除了小鎮法官）都信任這位小鎮法官。

隻有一個人同時滿足屬性 1 和屬性 2 。

給你一個數組 trust ，其中 trust[i] = [ai, bi] 表示編号為 ai 的人信任編号為 bi 的人。

如果小鎮法官存在并且可以确定他的身份，請傳回該法官的編号；否則，傳回 -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，不相信任何人 2.任何人都相信法官

就以上兩個點周遊數組就行了。

• 先周遊一遍數組找到所有 有信任别人的人，則這個人就不可能是法官,添加到數組 ordi_p 中，周遊結束，如果ordi_p 等于題目所給的小鎮人數n，則說明小鎮中沒有法官，直接傳回-1.
• 然後我們再次周遊該數組，構造哈希表。key存可能的法官，val存信任該法官的人數。
• 最後我們周遊哈希表，法官必須有 n-1個人信任他，也就是說val必須等于n-1，并且還不能再前面的ordi_p數組中，符合條件既是答案。

完整代碼:

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        if len(trust) == 0:
            if n == 1:
                return 1
            else:
                return -1
        hs = {}
        ordi_p = [] # 如果有相信的人, 則肯定不是法官
        for i in trust:
            ordi_p.append(i[0])
        if ordi_p == n:
            return -1
        print('這裡是ordi_p',ordi_p)
        for i in trust:
            # key 存可能的法官， val存信任法官的人數
            if i[1] not in  hs:
                hs[i[1]] = 1
            else:
                hs[i[1]] +=1
        print('這裡是hs',hs)
        # 法官需要有 n-1個人相信他
        for p in hs:
            if hs[p] == n-1 and p not in ordi_p:

                return p
        return -1