Сложность: medium
Предположим, вы находитесь на вечеринке с n людьми, обозначенными от 0 до n - 1, и среди них может быть один знаменитость. Определение знаменитости: все остальные n - 1 человек знают знаменитость, но знаменитость не знает никого из них.
Теперь вы хотите выяснить, кто является знаменитостью, или убедиться, что ее нет. Вам разрешено задавать вопросы типа: "Привет, A. Ты знаешь B?", чтобы получить информацию о том, знает ли A B. Вам нужно найти знаменитость (или убедиться, что ее нет), задав как можно меньше вопросов (в асимптотическом смысле).
Вам предоставлена вспомогательная функция bool knows(a, b), которая сообщает, знает ли a b. Реализуйте функцию int findCelebrity(n). На вечеринке будет ровно одна знаменитость, если она есть.
Верните метку знаменитости, если она есть на вечеринке. Если знаменитости нет, верните -1.
Пример:
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.
👨💻 Алгоритм:
1⃣Найти потенциального кандидата на знаменитость:
Использовать один проход через всех людей, чтобы определить возможного кандидата.
Если человек a знает человека b, то a не может быть знаменитостью, и переключаем кандидата на b.
2⃣Реализовать функцию isCelebrity(candidate):
Проверить, знает ли кандидат кого-либо из людей (исключая самих себя).
Проверить, знают ли все остальные кандидата (исключая самого кандидата).
Если кандидат знает кого-то, или кто-то не знает кандидата, то кандидат не является знаменитостью.
3⃣Возвращение результата:
Если кандидат проходит все проверки в isCelebrity(candidate), вернуть его метку.
В противном случае вернуть -1.
😎 Решение:
import 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));
}
}
Ставь 👍 и забирай 📚 Базу знаний