[LeetCode] 277. Find the Celebrity

jasperyang 发布于2019-08-19 11:12 / 1148人阅读

Problem

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.

Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity"s label if there is a celebrity in the party. If there is no celebrity, return -1.

Solution

Three cases:

Everyone knows someone else, return -1;

No one knows each other, return -1;

One doesn"t know anyone, every one else knows someone but not necessarily him, return -1;

Everyone knows him but he also knows someone, return -1;

Everyone knows him and he doesn"t know anyone, return suspect.

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int suspect = 0;
        for (int i = 1; i < n; i++) {
            //suspect shouldn"t know anyone, if he knows i, set i as new suspect
            if (knows(suspect, i)) suspect = i; 
        }
        for (int i = 0; i < n; i++) {
            //new suspect has been good so far, but double check
            if (i != suspect && (knows(suspect, i) || !knows(i, suspect))) return -1; 
        }
        return suspect;
    }
}

two for-loops with HashMap

if it removes the requirement that celebrity shouldn"t know anyone else, can do this:

public class Solution extends Relation {
    public int findCelebrity(int n) {
        Map map = new HashMap<>();
        List res = new ArrayList<>();
        for (int i = 0; i < n-1; i++) {
            for (int j = i+1; j < n; j++) {
                if (knows(i, j)) {
                    map.put(j, map.getOrDefault(j, 0)+1);
                }
                if (knows(j, i)) {
                    map.put(i, map.getOrDefault(i, 0)+1);
                }
                if (map.containsKey(i) && map.get(i) == n-1) res.add(i);
                if (map.containsKey(j) && map.get(j) == n-1) res.add(j);
            }
        }
        if (res.size() == 0 || res.size() > 1) return -1;
        return res.get(0);
    }
}

云服务器 GPU云服务器 Celebrity the LeetCode sdp for the webrtc

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77207.html

277. Find the Celebrity

摘要：题目解答每一次比较只有两种情况，是的话，那么肯定不是是的话，那么肯定不是所以一直比较到最后会留下一个，然后我们再验证这个是不是正解。题目：Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The defini...

chavesgu 2019-08-14 16:31 评论0 收藏0
【小工具】node.js下载json对象中包含的所有图片链接

摘要：我先是在浏览器上输入豆瓣的地址，拉下来数据。根据豆瓣的图片地址，建立了对应的文件夹以下逻辑代码中该函数的功能是接收一个数组数据的文件路径，就可以将该中包含的所有的图片路径全部下载到中下对应的文件夹中。今天在看微信小程序，数据是从网上找的API请求下来的。就想能不能把数据保存到本地来，以后没有网络也可以自己搭服务器提供数据。说干就干，我打算用node来做。我先是在浏览器上输入豆瓣的...

notebin 2019-08-20 17:14 评论0 收藏0
Python 面向对象编程OOP (二) slots，类的多态，继承，复写方法

摘要：需要注意的是的限定只对当前类的对象生效，对子类并不起任何作用。本文的实例名称均为杜撰，请不要对号入座我的其他文章已经放到了上，如果感兴趣的朋友可以去看看，链接如下精品练习题道实用技巧汇总教程 __slots__魔法大家好，上一期我重点总结了有关类的基本知识，现在简单回顾一下，顺便加上一个创建类时常用的东西：__slots__ 首先创建一个名人类：Celebrity class Ce...

Binguner 2019-07-31 11:28 评论0 收藏0
有坑勿踩（三）——关于数据更新

摘要：前言数据更新，中的，对任何数据库而言都是最基本的操作。你并不能保证数据在被你读出来到写回去期间是否有别人已经改了数据库中的记录，这就是第一个风险，操作存在潜在的可能性会覆盖掉别人更新过的数据。前言数据更新，CRUD中的U，对任何数据库而言都是最基本的操作。看似简单的更新操作中会藏着哪些坑？今天聊一聊这个话题。在写这个系列文章时，我会假设读者已经对MongoDB有了最基础的了解，因...

mengera88 2019-06-26 17:59 评论0 收藏0
Python爬虫实战: 通用版豆瓣电影数据及图片的获取与入库,含防呆逻辑

摘要：电影讲述由浩克斯扮演的酗酒前警察偶然发现一具女尸，并不慎将他的家庭至于危险之中，他不得不一边寻找凶手，一边与恶势力作斗争。该片由内尔姆斯兄弟执导，目前正在拍摄中。由于最近需要准备一些数据,故开始练习使用胶水语言,经过一番探索终于完成了豆瓣电影信息的爬取,特此分享. 需要说明的是,我这里把电影信息提取之后,缓存了电影封面和演职人员的图片,并对图片信息进行了获取入库先贴出我两种表结构:...

ckllj 2019-07-30 16:52 评论0 收藏0