[用 Python 解 LeetCode] (004) 277. Find the Celebrity

这题因为 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