解锁 Leetcode 新题：寻找明星
Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them. Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A. Do you know B?” to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense). You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.
还原题目的开放性
首先小编对这道题出现在 Leetcode 中表示吃惊，因为这是自己面试某知名社交网络公司 onsite 一道题目的变种。原题目其实有很更强的开放性，而在 Leetcode 里面，只把最 tricky 的部分展现了出来。
下面我们从这道题的开放性说起：
如果我们不去看那个 helper function bool knows(a, b), 这道题完全可以成为一道 OO design: 面试官可以去问面试者如何设计一个 Person Class 以及如何在 Class 中表现出人与人之间的 relationship, 然后使用 Person Class 实现寻找明星的算法。
Naive Solution
说到 relationship, 最 naive 的方式是在每个 Person Class 里面都建立一个 List 存储所有认识的人。显然在在上述的方法 cost 很高：不仅需要大量的空间，同时搜索名人的算法也相当繁琐。
另一种思路是想到通过建立一个有向图来表明人与人之间的关系。这样只需要遍历这个图，找到是否存在一个只有入度没有出度的点，并且这个点的入度等于所有点个数减一。这时候我们就把问题转换成图得遍历问题。
如何设计有向图和遍历有向图，在这里就不用为大家再次陈述了，有兴趣的同学可以点击 “阅读原文” 查看详细内容。
挖掘隐藏条件
回到 Leetcode 这道题目，让我们接下来深度挖掘这道题背后所隐藏的条件，像我们初高中解几何问题一样。
让我们回到名人的定义：The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.
有多少同学考虑过名人的数量问题?
我们从定义中不难看出，所谓名人，他/她既要被所有人都认识的同时还不能认识任何人，那么就意味着一群人之中，有且最多有1名人的存在。举个例子：
List: P1, P2, P3, P4 一共有四个人， “a->b” 表示 a 认识 b;
- P1->P2, P1->P3, P2->P3, P4->P3, P2->P4: 在这组关系中 P3 就是 celebrity;
- P1->P4, P1->P3, P2->P3, P2->P4: 在这组关系中虽然 P3, P4 都不认识其他人，但是他们都不是 celebrity;
换句话说，如果一群人中同时有 A, B 两位明星，对 A 来说，所有其他人都认识它，B 也不例外，但这与 B 是明星的定义不符。
回到题目本身，别忘了我们还有一个 helper function bool knows(a, b), 如何去灵活的运用这个 helper function?
让我们翻回头来思考一下名人的定义，再结合 knows() 函数所给出的结果：
- If Knows (a, b) == true, 说明 a 认识 b, 那么 a 是否还有可能成为 celebrity? 答案是否定的，因为根据 celebrity 的定义, 当 a 认识其他人的时候，a 一定不是 celebrity. 那么 b 有可能么? 答案是有可能。
- If Knows (a, b) == false, 说明 a 不认识 b, 那么 b 可能是 celebrity么? 答案是否定的，因为根据定义，名人被所有人都认识，所以 b 不是名人。
重要推论
通过上述的判断我们发现无论 knows(a, b) 的结果，我们都可以从 a/b 中排除其中一个当名人的可能。
我们只需要两两相互判断，一个个排除非名人，留到最后的就是潜在的名人。
最后找出来的那个人一定是 celebrity 么？
回头看看之前那个 P3, P4 都不认识其他人的例子，我们通过第一遍扫面只能找出那个有可能是名人的潜在人选，但我们无法完全确定他是否就是明星（想想为什么？），所以我们需要做第二次遍历来确认这个潜在的人选是否是名人。
代码
