資訊專欄INFORMATION COLUMN
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.
SolutionThree 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)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/77207.html
摘要：題目解答每一次比較只有兩種情況，是的話，那么肯定不是是的話，那么肯定不是所以一直比較到最后會留下一個，然后我們再驗證這個是不是正解。 題目：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...
摘要：我先是在瀏覽器上輸入豆瓣的地址，拉下來數(shù)據(jù)。根據(jù)豆瓣的圖片地址，建立了對應(yīng)的文件夾以下邏輯代碼中該函數(shù)的功能是接收一個數(shù)組數(shù)據(jù)的文件路徑，就可以將該中包含的所有的圖片路徑全部下載到中下對應(yīng)的文件夾中。 今天在看微信小程序，數(shù)據(jù)是從網(wǎng)上找的API請求下來的。就想能不能把數(shù)據(jù)保存到本地來，以后沒有網(wǎng)絡(luò)也可以自己搭服務(wù)器提供數(shù)據(jù)。 說干就干，我打算用node來做。 我先是在瀏覽器上輸入豆瓣的...
摘要：需要注意的是的限定只對當(dāng)前類的對象生效，對子類并不起任何作用。本文的實例名稱均為杜撰，請不要對號入座我的其他文章已經(jīng)放到了上，如果感興趣的朋友可以去看看，鏈接如下精品練習(xí)題道實用技巧匯總教程 __slots__魔法 大家好，上一期我重點總結(jié)了有關(guān)類的基本知識，現(xiàn)在簡單回顧一下，順便加上一個創(chuàng)建類時常用的東西：__slots__ 首先創(chuàng)建一個名人類：Celebrity class Ce...
摘要：前言數(shù)據(jù)更新，中的，對任何數(shù)據(jù)庫而言都是最基本的操作。你并不能保證數(shù)據(jù)在被你讀出來到寫回去期間是否有別人已經(jīng)改了數(shù)據(jù)庫中的記錄，這就是第一個風(fēng)險，操作存在潛在的可能性會覆蓋掉別人更新過的數(shù)據(jù)。 前言 數(shù)據(jù)更新，CRUD中的U，對任何數(shù)據(jù)庫而言都是最基本的操作?？此坪唵蔚母虏僮髦袝刂男┛樱拷裉炝囊涣倪@個話題。 在寫這個系列文章時，我會假設(shè)讀者已經(jīng)對MongoDB有了最基礎(chǔ)的了解，因...
摘要：電影講述由浩克斯扮演的酗酒前警察偶然發(fā)現(xiàn)一具女尸，并不慎將他的家庭至于危險之中，他不得不一邊尋找兇手，一邊與惡勢力作斗爭。該片由內(nèi)爾姆斯兄弟執(zhí)導(dǎo)，目前正在拍攝中。 由于最近需要準(zhǔn)備一些數(shù)據(jù),故開始練習(xí)使用膠水語言,經(jīng)過一番探索終于完成了豆瓣電影信息的爬取,特此分享. 需要說明的是,我這里把電影信息提取之后,緩存了電影封面和演職人員的圖片,并對圖片信息進行了獲取入庫 先貼出我兩種表結(jié)構(gòu):...
閱讀 2048·2023-04-25 15:45
閱讀 1440·2021-09-29 09:34
閱讀 2578·2021-09-03 10:30
閱讀 2081·2019-08-30 15:56
閱讀 1512·2019-08-29 15:31
閱讀 1334·2019-08-29 15:29
閱讀 3257·2019-08-29 11:24
閱讀 3118·2019-08-26 13:45
