277. Find the Celebrity

chavesgu 發布于2019-08-14 16:31 / 2014人閱讀

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

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

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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對象中包含的所有圖片鏈接

摘要：我先是在瀏覽器上輸入豆瓣的地址，拉下來數據。根據豆瓣的圖片地址，建立了對應的文件夾以下邏輯代碼中該函數的功能是接收一個數組數據的文件路徑，就可以將該中包含的所有的圖片路徑全部下載到中下對應的文件夾中。今天在看微信小程序，數據是從網上找的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