721. Accounts Merge
Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.
Дан список аккаунтов, в котором каждый element accounts[i] - это список строк, где первый element accounts[i][0] - это имя, а остальные elementы - это email, представляющие электронную почту аккаунта. Теперь мы хотим объединить эти аккаунты. Два аккаунта определенно принадлежат одному человеку, если у обоих аккаунтов есть какой-то общий email. Обратите внимание, что даже если два аккаунта имеют одинаковое имя, они могут принадлежать разным людям, поскольку у людей могут быть одинаковые имена. Изначально у человека может быть любое количество счетов, но все его счета обязательно должны иметь одинаковое имя. После объединения счетов return счета в следующем формате: первый element каждого счета - имя, а остальные elementы - электронные письма в отсортированном порядке. Сами аккаунты могут быть возвращены в любом порядке.
Exemple:
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"]]
C# solution
correspondant/originalusing System;
using System.Collections.Generic;
public class Solution {
public IList<IList<string>> AccountsMerge(IList<IList<string>> accounts) {
var emailToName = new Dictionary<string, string>();
var graph = new Dictionary<string, HashSet<string>>();
foreach (var account in accounts) {
string name = account[0];
string firstEmail = account[1];
foreach (var email in account.Skip(1)) {
if (!graph.ContainsKey(firstEmail)) graph[firstEmail] = new HashSet<string>();
if (!graph.ContainsKey(email)) graph[email] = new HashSet<string>();
graph[firstEmail].Add(email);
graph[email].Add(firstEmail);
emailToName[email] = name;
}
}
var seen = new HashSet<string>();
var mergedAccounts = new List<IList<string>>();
foreach (var email in emailToName.Keys) {
if (!seen.Contains(email)) {
var emails = new List<string>();
var stack = new Stack<string>();
stack.Push(email);
while (stack.Count > 0) {
var node = stack.Pop();
if (!seen.Contains(node)) {
seen.Add(node);
emails.Add(node);
foreach (var neighbor in graph[node]) {
stack.Push(neighbor);
}
}
}
emails.Sort();
mergedAccounts.Add(new List<string> { emailToName[email] });
mergedAccounts[mergedAccounts.Count - 1].AddRange(emails);
}
}
return mergedAccounts;
}
}C++ solution
brouillon automatique, à relire avant soumission#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:
public IList<vector<string>> AccountsMerge(IList<vector<string>> accounts) {
var emailToName = new unordered_map<string, string>();
var graph = new unordered_map<string, HashSet<string>>();
foreach (var account in accounts) {
string name = account[0];
string firstEmail = account[1];
foreach (var email in account.Skip(1)) {
if (!graph.count(firstEmail)) graph[firstEmail] = new HashSet<string>();
if (!graph.count(email)) graph[email] = new HashSet<string>();
graph[firstEmail].push_back(email);
graph[email].push_back(firstEmail);
emailToName[email] = name;
}
}
var seen = new HashSet<string>();
var mergedAccounts = new List<vector<string>>();
foreach (var email in emailToName.Keys) {
if (!seen.Contains(email)) {
var emails = new List<string>();
var stack = new stack<string>();
stack.push(email);
while (stack.size() > 0) {
var node = stack.pop();
if (!seen.Contains(node)) {
seen.push_back(node);
emails.push_back(node);
foreach (var neighbor in graph[node]) {
stack.push(neighbor);
}
}
}
emails.Sort();
mergedAccounts.push_back(new List<string> { emailToName[email] });
mergedAccounts[mergedAccounts.size() - 1].AddRange(emails);
}
}
return mergedAccounts;
}
}Java solution
correspondant/originalimport java.util.*;
public class Solution {
public List<List<String>> accountsMerge(List<List<String>> accounts) {
Map<String, String> emailToName = new HashMap<>();
Map<String, Set<String>> graph = new HashMap<>();
for (List<String> account : accounts) {
String name = account.get(0);
String firstEmail = account.get(1);
for (String email : account.subList(1, account.size())) {
graph.computeIfAbsent(firstEmail, x -> new HashSet<>()).add(email);
graph.computeIfAbsent(email, x -> new HashSet<>()).add(firstEmail);
emailToName.put(email, name);
}
}
Set<String> seen = new HashSet<>();
List<List<String>> mergedAccounts = new ArrayList<>();
for (String email : emailToName.keySet()) {
if (!seen.contains(email)) {
List<String> emails = new ArrayList<>();
Stack<String> stack = new Stack<>();
stack.push(email);
while (!stack.isEmpty()) {
String node = stack.pop();
if (!seen.contains(node)) {
seen.add(node);
emails.add(node);
for (String neighbor : graph.get(node)) {
stack.push(neighbor);
}
}
}
Collections.sort(emails);
mergedAccounts.add(new ArrayList<>(Arrays.asList(emailToName.get(email))));
mergedAccounts.get(mergedAccounts.size() - 1).addAll(emails);
}
}
return mergedAccounts;
}
}JavaScript solution
correspondant/originalvar accountsMerge = function(accounts) {
const emailToName = {};
const graph = {};
for (let account of accounts) {
const name = account[0];
const firstEmail = account[1];
for (let email of account.slice(1)) {
if (!graph[firstEmail]) graph[firstEmail] = new Set();
if (!graph[email]) graph[email] = new Set();
graph[firstEmail].add(email);
graph[email].add(firstEmail);
emailToName[email] = name;
}
}
const seen = new Set();
const dfs = (email) => {
const stack = [email];
const result = [];
while (stack.length) {
const node = stack.pop();
if (!seen.has(node)) {
seen.add(node);
result.push(node);
for (let neighbor of graph[node]) {
stack.push(neighbor);
}
}
}
return result;
};
const mergedAccounts = [];
for (let email in emailToName) {
if (!seen.has(email)) {
const emails = dfs(email);
mergedAccounts.push([emailToName[email], ...emails.sort()]);
}
}
return mergedAccounts;
};Python solution
correspondant/originaldef accountsMerge(accounts):
from collections import defaultdict
graph = defaultdict(set)
email_to_name = {}
for account in accounts:
name = account[0]
first_email = account[1]
for email in account[1:]:
graph[first_email].add(email)
graph[email].add(first_email)
email_to_name[email] = name
visited = set()
merged_accounts = []
def dfs(email):
emails = [email]
stack = [email]
while stack:
node = stack.pop()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)
emails.append(neighbor)
return emails
for email in graph:
if email not in visited:
visited.add(email)
emails = dfs(email)
merged_accounts.append([email_to_name[email]] + sorted(emails))
return merged_accountsGo solution
correspondant/originalpackage main
import (
"sort"
)
func accountsMerge(accounts [][]string) [][]string {
emailToName := make(map[string]string)
graph := make(map[string]map[string]struct{})
for _, account := range accounts {
name := account[0]
firstEmail := account[1]
for _, email := range account[1:] {
if graph[firstEmail] == nil {
graph[firstEmail] = make(map[string]struct{})
}
if graph[email] == nil {
graph[email] = make(map[string]struct{})
}
graph[firstEmail][email] = struct{}{}
graph[email][firstEmail] = struct{}{}
emailToName[email] = name
}
}
seen := make(map[string]struct{})
var mergedAccounts [][]string
for email := range emailToName {
if _, ok := seen[email]; !ok {
var emails []string
stack := []string{email}
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if _, ok := seen[node]; !ok {
seen[node] = struct{}{}
emails = append(emails, node)
for neighbor := range graph[node] {
stack = append(stack, neighbor)
}
}
}
sort.Strings(emails)
account := append([]string{emailToName[email]}, emails...)
mergedAccounts = append(mergedAccounts, account)
}
}
return mergedAccounts
}Algorithm
Создайте graphe, в котором узлы представляют email-адреса, а ребра соединяют email-адреса, принадлежащие одному аккаунту.
Пройдите по grapheу, чтобы find все связанные компоненты, которые представляют объединенные аккаунты.
Для каждой связанной компоненты, соберите email-адреса, отсортируйте их и добавьте имя пользователя в начало списка.
😎
Vacancies for this task
offres actives with overlapping task tags are affichés.
Il n'y a pas encore d'offres actives.