解锁 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 都不认识其他人的例子,我们通过第一遍扫面只能找出那个有可能是名人的潜在人选,但我们无法完全确定他是否就是明星(想想为什么?),所以我们需要做第二次遍历来确认这个潜在的人选是否是名人。

代码

原文发布于微信公众号 - 包子铺里聊IT(baozitraining)

原文发表时间:2015-10-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能头条

知识图谱系列 | 知识图谱的前世今生与RDF的实践

【人工智能头条导读】本文是我们知识图谱系列的第二篇文章,希望人工智能头条为大家准备的文章对大家的学习有更多的帮助。

6092
来自专栏我是攻城师

统计学里面的百分位数是什么意思

6025
来自专栏数据派THU

独家 | 带你入门比Python更高效的Numpy(附代码)

向量化技巧对于数据科学家来说是相当熟知的,并且常用于编程中,以加速整体数据转换,其中简单的数学变化通过可迭代对象(例如列表)执行。未受到重视的是,把有一定规模的...

1133
来自专栏恰童鞋骚年

自己动手写游戏:坦克撕逼大战

START:最近在公交车上无聊,于是用平板看了看下载的坦克大战的开发教程,于是在晚上回家后花了两天模仿了一个,现在来总结一下。

1936
来自专栏数据小魔方

空间数据可视化与simple future模型应用

这是一篇关于关于空间地理信息数据可视化与simple feature 模型应用的笔记小结。

1483
来自专栏算法channel

动态规划|相邻约束下的最优解

本篇进一步介绍动态规划的基本应用。 1 题目 You are a professional robber planning to rob houses alon...

3874
来自专栏算法channel

动态规划中篇:爬楼梯

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。 0...

4099
来自专栏ThoughtWorks

像机器一样思考|TW洞见

今日洞见 文章作者、部分图片来自ThoughtWorks:仝键。 本文所有内容,包括文字、图片和音视频资料,版权均属ThoughtWorks公司所有,任何媒体、...

3747
来自专栏好好学java的技术栈

“365算法每日学计划”:01打卡

如果有小伙伴很少接触到这种题目的话,可能会觉得有点陌生,不知道从何下手,可能一开始我们能想到“最笨”的方法,但是也觉得挺有“娱乐性”的方法。

2803
来自专栏racaljk

当我们谈论计算机科学

下午偶有所悟,特作此文防止青年痴呆。 这学期的学习算是走了一半计算机科学概论。广度的学习通常会被指责为广而不精,但对我而言这是毫无意义的,因为 ...

1054

扫码关注云+社区

领取腾讯云代金券