Сложность: 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.
😎 Решение:
class Solution {
private $n;
private $cache = [];
function findCelebrity($n) {
$this->n = $n;
$celebrityCandidate = 0;
for ($i = 1; $i < $n; $i++) {
if ($this->cachedKnows($celebrityCandidate, $i)) {
$celebrityCandidate = $i;
}
}
return $this->isCelebrity($celebrityCandidate) ? $celebrityCandidate : -1;
}
private function isCelebrity($i) {
for ($j = 0; $j < $this->n; $j++) {
if ($i == $j) continue;
if ($this->cachedKnows($i, $j) || !$this->cachedKnows($j, $i)) {
return false;
}
}
return true;
}
private function cachedKnows($a, $b) {
$key = "$a,$b";
if (!isset($this->cache[$key])) {
$this->cache[$key] = knows($a, $b);
}
return $this->cache[$key];
}
}Ставь 👍 и забирай 📚 Базу знаний