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

这题因为 leetcode锁起来，所以我们跑去做Lintcode上面的第 645题 Find the Celebrity

题干懒人包

从派对里面找名人，要是名人的条件有二

大家都认识他他不认识任何人

可以利用它提供的 API 获取A是否认识B，比方说这样调用Celebrity.knows(a, b)，返回值是True 代表认识，False代表不认识。

一个派对最多只有一个名人，如果有名人回传他的下标值，没有的话回传 -1。目标是调用最少次题目提供的 API

解法

首先假设第一个人是名人(用head 表示现在谁有可能是名人)，开始循环剩下人，思维有以下两个

如果 head 知道下一个人是谁，就代表 head 一定不是名人，所以现在第 i 个人有可能是如果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