這題因為 leetcode鎖起來，所以我們跑去做Lintcode上面的第 645題 Find the Celebrity

題幹懶人包

從派對裡面找名人，要是名人的條件有二

1. 大家都認識他
2. 他不認識任何人

可以利用它提供的 API 獲取A是否認識B，比方說這樣調用Celebrity.knows(a, b)，返回值是True 代表認識，False代表不認識。

一個派對最多只有一個名人，如果有名人回傳他的下標值，沒有的話回傳 -1。目標是調用最少次題目提供的 API

解法

首先假設第一個人是名人(用head 表示現在誰有可能是名人)，開始循環剩下人，思維有以下兩個

1. 如果 head 知道下一個人是誰，就代表 head 一定不是名人，所以現在第 i 個人有可能是
2. 如果head 不知道下一個人是誰，下一個人就一定不是名人，head 保持不變

如此循環完成後，可以得到 head 現在是最有可能是名人的人，然後他不認識大家沒有用，還必須要大家都認識他，因此循環一次，一但有人不認識他，代表所有人裡面沒有人還有可能是名人。

最後因為一直以來 head 都是不知道 head 以後的人是誰，所以 head 還有可能知道他前面的人是誰。因此還需要跑一次迴圈確定前面的人他都不認識。

class Solution:
    # @param {int} n a party with n people
    # @return {int} the celebrity's label or -1
    
    def findCelebrity(self, n):
        # 首先假設第一個人是名人(用head 表示現在誰有可能是名人)
        head = 0
        for i in range(1, n):
            # 如果head 不知道下一個人是誰，下一個人就一定不是名人，head 保持不變
            if not Celebrity.knows(head, i):
                continue
            # 如果 head 知道下一個人是誰，就代表 head 一定不是名人，所以現在第 i 個人有可能是
            else:
                head = i
        # 還必須要大家都認識他，因此循環一次
        for i in range(n):
            if not Celebrity.knows(i, head):
                head = -1
                break
        # head 還有可能知道他前面的人是誰。因此還需要跑一次迴圈        
        for i in range(0, head):
            if Celebrity.knows(head, i):
                head = -1
                break
        return head