277. Find the Celebrity

chavesgu 發(fā)布于2019-08-14 16:31 / 2018人閱讀

摘要：題目解答每一次比較只有兩種情況，是的話，那么肯定不是是的話，那么肯定不是所以一直比較到最后會留下一個，然后我們再驗證這個是不是正解。

題目：
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.

解答：

/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int candidate = 0;
        //每一次比較只有兩種情況，knows(a, b)是true的話，那么a肯定不是candidate; knows(a, b)是false的話，那么b肯定不是candidate. 所以一直比較到最后會留下一個candidate，然后我們再驗證這個是不是正解。
        for (int i = 1; i < n; i++) {
            if (knows(candidate, i)) {
                candidate = i;
            }
        }
        for (int i = 0; i < n; i++) {
            if (candidate != i && (knows(candidate, i) || !knows(i, candidate))) {
                return -1;
            }
        }
        return candidate;
    }
}

云服務器 GPU云服務器 Celebrity the sdp for the webrtc find

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://systransis.cn/yun/66211.html

[LeetCode] 277. Find the Celebrity

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 ...

jasperyang 2019-08-19 11:12 評論0 收藏0
【小工具】node.js下載json對象中包含的所有圖片鏈接

摘要：我先是在瀏覽器上輸入豆瓣的地址，拉下來數(shù)據(jù)。根據(jù)豆瓣的圖片地址，建立了對應的文件夾以下邏輯代碼中該函數(shù)的功能是接收一個數(shù)組數(shù)據(jù)的文件路徑，就可以將該中包含的所有的圖片路徑全部下載到中下對應的文件夾中。今天在看微信小程序，數(shù)據(jù)是從網(wǎng)上找的API請求下來的。就想能不能把數(shù)據(jù)保存到本地來，以后沒有網(wǎng)絡也可以自己搭服務器提供數(shù)據(jù)。說干就干，我打算用node來做。我先是在瀏覽器上輸入豆瓣的...

notebin 2019-08-20 17:14 評論0 收藏0
Python 面向對象編程OOP (二) slots，類的多態(tài)，繼承，復寫方法

摘要：需要注意的是的限定只對當前類的對象生效，對子類并不起任何作用。本文的實例名稱均為杜撰，請不要對號入座我的其他文章已經(jīng)放到了上，如果感興趣的朋友可以去看看，鏈接如下精品練習題道實用技巧匯總教程 __slots__魔法大家好，上一期我重點總結了有關類的基本知識，現(xiàn)在簡單回顧一下，順便加上一個創(chuàng)建類時常用的東西：__slots__ 首先創(chuàng)建一個名人類：Celebrity class Ce...

Binguner 2019-07-31 11:28 評論0 收藏0
有坑勿踩（三）——關于數(shù)據(jù)更新

摘要：前言數(shù)據(jù)更新，中的，對任何數(shù)據(jù)庫而言都是最基本的操作。你并不能保證數(shù)據(jù)在被你讀出來到寫回去期間是否有別人已經(jīng)改了數(shù)據(jù)庫中的記錄，這就是第一個風險，操作存在潛在的可能性會覆蓋掉別人更新過的數(shù)據(jù)。前言數(shù)據(jù)更新，CRUD中的U，對任何數(shù)據(jù)庫而言都是最基本的操作?？此坪唵蔚母虏僮髦袝刂男┛?？今天聊一聊這個話題。在寫這個系列文章時，我會假設讀者已經(jīng)對MongoDB有了最基礎的了解，因...

mengera88 2019-06-26 17:59 評論0 收藏0
Python爬蟲實戰(zhàn): 通用版豆瓣電影數(shù)據(jù)及圖片的獲取與入庫,含防呆邏輯

摘要：電影講述由浩克斯扮演的酗酒前警察偶然發(fā)現(xiàn)一具女尸，并不慎將他的家庭至于危險之中，他不得不一邊尋找兇手，一邊與惡勢力作斗爭。該片由內(nèi)爾姆斯兄弟執(zhí)導，目前正在拍攝中。由于最近需要準備一些數(shù)據(jù),故開始練習使用膠水語言,經(jīng)過一番探索終于完成了豆瓣電影信息的爬取,特此分享. 需要說明的是,我這里把電影信息提取之后,緩存了電影封面和演職人員的圖片,并對圖片信息進行了獲取入庫先貼出我兩種表結構:...

ckllj 2019-07-30 16:52 評論0 收藏0