277. Find the Celebrity
Предположим, вы находитесь на вечеринке с n людьми, обозначенными от 0 до n - 1, и среди них может быть один знаменитость. Definition знаменитости: все остальные n - 1 человек знают знаменитость, но знаменитость не знает никого из них. Теперь вы хотите выяснить, кто является знаменитостью, или убедиться, что ее нет. Вам разрешено задавать вопросы типа: "Привет, A. Ты знаешь B?", чтобы получить информацию о том, знает ли A B. Вам нужно find знаменитость (или убедиться, что ее нет), задав как можно меньше вопросов (в асимптотическом смысле).
Вам предоставлена вспомогательная функция bool knows(a, b), которая сообщает, знает ли a b. Реализуйте функцию int findCelebrity(n). На вечеринке будет ровно одна знаменитость, если она есть.
return метку знаменитости, если она есть на вечеринке. Если знаменитости нет, return -1.
Example:
Input: graph = [[1,1,0],[0,1,0],[1,1,1]]
Output: 1
Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is the person labeled as 1 because both 0 and 2 know him but 1 does not know anybody.
C# solution
matched/originalpublic class Solution {
private int n;
private Dictionary<Tuple<int, int>, bool> cache = new Dictionary<Tuple<int, int>, bool>();
public int FindCelebrity(int n) {
this.n = n;
int celebrityCandidate = 0;
for (int i = 1; i < n; i++) {
if (CachedKnows(celebrityCandidate, i)) {
celebrityCandidate = i;
}
}
return IsCelebrity(celebrityCandidate) ? celebrityCandidate : -1;
}
private bool IsCelebrity(int i) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
if (CachedKnows(i, j) || !CachedKnows(j, i)) {
return false;
}
}
return true;
}
private bool CachedKnows(int a, int b) {
var key = Tuple.Create(a, b);
if (!cache.ContainsKey(key)) {
cache[key] = Knows(a, b);
}
return cache[key];
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
private int n;
private unordered_map<Tuple<int, int>, bool> cache = new unordered_map<Tuple<int, int>, bool>();
public int FindCelebrity(int n) {
this.n = n;
int celebrityCandidate = 0;
for (int i = 1; i < n; i++) {
if (CachedKnows(celebrityCandidate, i)) {
celebrityCandidate = i;
}
}
return IsCelebrity(celebrityCandidate) ? celebrityCandidate : -1;
}
private bool IsCelebrity(int i) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
if (CachedKnows(i, j) || !CachedKnows(j, i)) {
return false;
}
}
return true;
}
private bool CachedKnows(int a, int b) {
var key = Tuple.Create(a, b);
if (!cache.count(key)) {
cache[key] = Knows(a, b);
}
return cache[key];
}
}Java solution
matched/originalimport java.util.HashMap;
import java.util.Map;
public class Solution {
private int n;
private Map<String, Boolean> cache = new HashMap<>();
public int findCelebrity(int n) {
this.n = n;
int celebrityCandidate = 0;
for (int i = 1; i < n; i++) {
if (cachedKnows(celebrityCandidate, i)) {
celebrityCandidate = i;
}
}
return isCelebrity(celebrityCandidate) ? celebrityCandidate : -1;
}
private boolean isCelebrity(int i) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
if (cachedKnows(i, j) || !cachedKnows(j, i)) {
return false;
}
}
return true;
}
private boolean cachedKnows(int a, int b) {
String key = a + "," + b;
return cache.computeIfAbsent(key, k -> knows(a, b));
}
}JavaScript solution
matched/originalvar Solution = function() {
this.n = 0;
this.cache = new Map();
};
Solution.prototype.findCelebrity = function(n) {
this.n = n;
let celebrityCandidate = 0;
for (let i = 1; i < n; i++) {
if (this.cachedKnows(celebrityCandidate, i)) {
celebrityCandidate = i;
}
}
return this.isCelebrity(celebrityCandidate) ? celebrityCandidate : -1;
};
Solution.prototype.isCelebrity = function(i) {
for (let j = 0; j < this.n; j++) {
if (i === j) continue;
if (this.cachedKnows(i, j) || !this.cachedKnows(j, i)) {
return false;
}
}
return true;
};
Solution.prototype.cachedKnows = function(a, b) {
const key = `${a},${b}`;
if (!this.cache.has(key)) {
this.cache.set(key, knows(a, b));
}
return this.cache.get(key);
};Python solution
matched/originalfrom functools import lru_cache
class Solution:
@lru_cache(maxsize=None)
def cachedKnows(self, a, b):
return knows(a, b)
def findCelebrity(self, n: int) -> int:
self.n = n
celebrity_candidate = 0
for i in range(1, n):
if self.cachedKnows(celebrity_candidate, i):
celebrity_candidate = i
if self.is_celebrity(celebrity_candidate):
return celebrity_candidate
return -1
def is_celebrity(self, i):
for j in range(self.n):
if i == j: continue
if self.cachedKnows(i, j) or not self.cachedKnows(j, i):
return False
return TrueGo solution
matched/originaltype Solution struct {
n int
cache map[pair]bool
}
type pair struct {
a, b int
}
func (s *Solution) findCelebrity(n int) int {
s.n = n
s.cache = make(map[pair]bool)
celebrityCandidate := 0
for i := 1; i < n; i++ {
if s.cachedKnows(celebrityCandidate, i) {
celebrityCandidate = i
}
}
if s.isCelebrity(celebrityCandidate) {
return celebrityCandidate
}
return -1
}
func (s *Solution) isCelebrity(i int) bool {
for j := 0; j < s.n; j++ {
if i == j {
continue
}
if s.cachedKnows(i, j) || !s.cachedKnows(j, i) {
return false
}
}
return true
}
func (s *Solution) cachedKnows(a, b int) bool {
key := pair{a, b}
if _, exists := s.cache[key]; !exists {
s.cache[key] = knows(a, b)
}
return s.cache[key]
}Algorithm
find потенциального кандидата на знаменитость:
Использовать один проход через всех людей, чтобы определить возможного кандидата.
Если человек a знает человека b, то a не может быть знаменитостью, и переключаем кандидата на b.
Реализовать функцию isCelebrity(candidate):
Проверить, знает ли кандидат кого-либо из людей (исключая самих себя).
Проверить, знают ли все остальные кандидата (исключая самого кандидата).
Если кандидат знает кого-то, или кто-то не знает кандидата, то кандидат не является знаменитостью.
Возвращение результата:
Если кандидат проходит все проверки в isCelebrity(candidate), вернуть его метку.
В противном случае вернуть -1.
😎
Vacancies for this task
Active vacancies with overlapping task tags are shown.