国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專(zhuān)欄INFORMATION COLUMN

[LeetCode] 277. Find the Celebrity

jasperyang / 1149人閱讀

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);
    }
}

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

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/77207.html

相關(guān)文章

  • 277. Find the Celebrity

    摘要:題目解答每一次比較只有兩種情況,是的話,那么肯定不是是的話,那么肯定不是所以一直比較到最后會(huì)留下一個(gè),然后我們?cè)衮?yàn)證這個(gè)是不是正解。 題目: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 評(píng)論0 收藏0
  • 【小工具】node.js下載json對(duì)象中包含的所有圖片鏈接

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

    notebin 評(píng)論0 收藏0
  • Python 面向?qū)ο缶幊蘋(píng)OP (二) slots,類(lèi)的多態(tài),繼承,復(fù)寫(xiě)方法

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

    Binguner 評(píng)論0 收藏0
  • 有坑勿踩(三)——關(guān)于數(shù)據(jù)更新

    摘要:前言數(shù)據(jù)更新,中的,對(duì)任何數(shù)據(jù)庫(kù)而言都是最基本的操作。你并不能保證數(shù)據(jù)在被你讀出來(lái)到寫(xiě)回去期間是否有別人已經(jīng)改了數(shù)據(jù)庫(kù)中的記錄,這就是第一個(gè)風(fēng)險(xiǎn),操作存在潛在的可能性會(huì)覆蓋掉別人更新過(guò)的數(shù)據(jù)。 前言 數(shù)據(jù)更新,CRUD中的U,對(duì)任何數(shù)據(jù)庫(kù)而言都是最基本的操作。看似簡(jiǎn)單的更新操作中會(huì)藏著哪些坑?今天聊一聊這個(gè)話題。 在寫(xiě)這個(gè)系列文章時(shí),我會(huì)假設(shè)讀者已經(jīng)對(duì)MongoDB有了最基礎(chǔ)的了解,因...

    mengera88 評(píng)論0 收藏0
  • Python爬蟲(chóng)實(shí)戰(zhàn): 通用版豆瓣電影數(shù)據(jù)及圖片的獲取與入庫(kù),含防呆邏輯

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

    ckllj 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<