Сайт: https://easyoffer.ru/
Все каналы: t.me/+xGeAw6ckJ4liYzQy
Контакт для рекламы: @sendme_ads
Post #1033
116
Задача: 1101. The Earliest Moment When Everyone Become Friends
Сложность: medium
В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi.
Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b.
Верните самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, верните -1.
Пример:
👨💻 Алгоритм:
1⃣Отсортируйте логи по времени в хронологическом порядке, так как в задаче не указано, отсортированы ли они.
2⃣Пройдитесь по отсортированным логам, применяя структуру данных "Объединение-Поиск":
Для каждого лога объедините двух участников, упомянутых в логе, с помощью функции union(a, b).
Каждое объединение добавляет новые связи между участниками.
3⃣Следите за количеством групп:
Изначально каждый участник рассматривается как отдельная группа.
Количество групп уменьшается с каждым полезным объединением.
Момент, когда количество групп уменьшается до одной, является самым ранним моментом, когда все участники становятся связанными (друзьями). Верните этот момент времени.
Если такого момента не существует, верните -1.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi.
Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b.
Верните самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, верните -1.
Пример:
Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
Output: 3
Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.
👨💻 Алгоритм:
1⃣Отсортируйте логи по времени в хронологическом порядке, так как в задаче не указано, отсортированы ли они.
2⃣Пройдитесь по отсортированным логам, применяя структуру данных "Объединение-Поиск":
Для каждого лога объедините двух участников, упомянутых в логе, с помощью функции union(a, b).
Каждое объединение добавляет новые связи между участниками.
3⃣Следите за количеством групп:
Изначально каждый участник рассматривается как отдельная группа.
Количество групп уменьшается с каждым полезным объединением.
Момент, когда количество групп уменьшается до одной, является самым ранним моментом, когда все участники становятся связанными (друзьями). Верните этот момент времени.
Если такого момента не существует, верните -1.
😎 Решение:
class UnionFind {
private $parent;
private $rank;
public function __construct($n) {
$this->parent = range(0, $n - 1);
$this->rank = array_fill(0, $n, 1);
}
public function find($x) {
if ($this->parent[$x] != $x) {
$this->parent[$x] = $this->find($this->parent[$x]);
}
return $this->parent[$x];
}
public function union($x, $y) {
$rootX = $this->find($x);
$rootY = $this->find($y);
if ($rootX != $rootY) {
if ($this->rank[$rootX] > $this->rank[$rootY]) {
$this->parent[$rootY] = $rootX;
} else if ($this->rank[$rootX] < $this->rank[$rootY]) {
$this->parent[$rootX] = $rootY;
} else {
$this->parent[$rootY] = $rootX;
$this->rank[$rootX]++;
}
return true;
}
return false;
}
}
class Solution {
function earliestAcq($logs, $n) {
usort($logs, function($a, $b) {
return $a[0] - $b[0];
});
$uf = new UnionFind($n);
$groupCount = $n;
foreach ($logs as $log) {
$timestamp = $log[0];
$friendA = $log[1];
$friendB = $log[2];
if ($uf->union($friendA, $friendB)) {
$groupCount--;
}
if ($groupCount == 1) {
return $timestamp;
}
}
return -1;
}
}Ставь 👍 и забирай 📚 Базу знаний
