Теория, подготовка к интервью и курсы для PHP разработчиков
YeaHub — это платформа для IT-специалистов, объединяющая обучение, карьерный рост, развитие и сообщество единомышленников.
Платформа: https://yeahub.ru
Для связи: @ruslan_kuyanets
Post #380
115
#ЛитКод
Задача: 721. Accounts Merge
Дан список аккаунтов, в котором каждый элемент accounts[i] - это список строк, где первый элемент accounts[i][0] - это имя, а остальные элементы - это email, представляющие электронную почту аккаунта. Теперь мы хотим объединить эти аккаунты. Два аккаунта определенно принадлежат одному человеку, если у обоих аккаунтов есть какой-то общий email. Обратите внимание, что даже если два аккаунта имеют одинаковое имя, они могут принадлежать разным людям, поскольку у людей могут быть одинаковые имена. Изначально у человека может быть любое количество счетов, но все его счета обязательно должны иметь одинаковое имя. После объединения счетов верните счета в следующем формате: первый элемент каждого счета - имя, а остальные элементы - электронные письма в отсортированном порядке. Сами аккаунты могут быть возвращены в любом порядке.
Пример:
👨💻 Алгоритм:
1⃣Создайте граф, в котором узлы представляют email-адреса, а ребра соединяют email-адреса, принадлежащие одному аккаунту.
2⃣Пройдите по графу, чтобы найти все связанные компоненты, которые представляют объединенные аккаунты.
3⃣Для каждой связанной компоненты, соберите email-адреса, отсортируйте их и добавьте имя пользователя в начало списка.
😎 Решение:
👉Новости 👉База вопросов
Задача: 721. Accounts Merge
Дан список аккаунтов, в котором каждый элемент accounts[i] - это список строк, где первый элемент accounts[i][0] - это имя, а остальные элементы - это email, представляющие электронную почту аккаунта. Теперь мы хотим объединить эти аккаунты. Два аккаунта определенно принадлежат одному человеку, если у обоих аккаунтов есть какой-то общий email. Обратите внимание, что даже если два аккаунта имеют одинаковое имя, они могут принадлежать разным людям, поскольку у людей могут быть одинаковые имена. Изначально у человека может быть любое количество счетов, но все его счета обязательно должны иметь одинаковое имя. После объединения счетов верните счета в следующем формате: первый элемент каждого счета - имя, а остальные элементы - электронные письма в отсортированном порядке. Сами аккаунты могут быть возвращены в любом порядке.
Пример:
nput: accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Output: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
👨💻 Алгоритм:
1⃣Создайте граф, в котором узлы представляют email-адреса, а ребра соединяют email-адреса, принадлежащие одному аккаунту.
2⃣Пройдите по графу, чтобы найти все связанные компоненты, которые представляют объединенные аккаунты.
3⃣Для каждой связанной компоненты, соберите email-адреса, отсортируйте их и добавьте имя пользователя в начало списка.
😎 Решение:
function accountsMerge($accounts) {
$emailToName = [];
$graph = [];
foreach ($accounts as $account) {
$name = $account[0];
$firstEmail = $account[1];
foreach (array_slice($account, 1) as $email) {
if (!isset($graph[$firstEmail])) $graph[$firstEmail] = [];
if (!isset($graph[$email])) $graph[$email] = [];
$graph[$firstEmail][] = $email;
$graph[$email][] = $firstEmail;
$emailToName[$email] = $name;
}
}
$seen = [];
$mergedAccounts = [];
foreach ($emailToName as $email => $name) {
if (!isset($seen[$email])) {
$emails = [];
$stack = [$email];
while (!empty($stack)) {
$node = array_pop($stack);
if (!isset($seen[$node])) {
$seen[$node] = true;
$emails[] = $node;
foreach ($graph[$node] as $neighbor) {
$stack[] = $neighbor;
}
}
}
sort($emails);
$mergedAccounts[] = array_merge([$name], $emails);
}
}
return $mergedAccounts;
}👉Новости 👉База вопросов
