LWC 57:721. Accounts Merge

LWC 57:721. Accounts Merge

传送门:721. Accounts Merge

Problem:

Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account. Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some email that is common to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name. After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Example 1:

Input: accounts = [[“John”, “johnsmith@mail.com”, “john00@mail.com”], [“John”, “johnnybravo@mail.com”], [“John”, “johnsmith@mail.com”, “john_newyork@mail.com”], [“Mary”, “mary@mail.com”]] Output: [[“John”, ‘john00@mail.com’, ‘john_newyork@mail.com’, ‘johnsmith@mail.com’], [“John”, “johnnybravo@mail.com”], [“Mary”, “mary@mail.com”]] Explanation: The first and third John’s are the same person as they have the common email “johnsmith@mail.com”. The second John and Mary are different people as none of their email addresses are used by other accounts. We could return these lists in any order, for example the answer [[‘Mary’, ‘mary@mail.com’], [‘John’, ‘johnnybravo@mail.com’], [‘John’, ‘john00@mail.com’, ‘john_newyork@mail.com’, ‘johnsmith@mail.com’]] would still be accepted.

Note:

The length of accounts will be in the range [1, 1000

The length of accounts[i] will be in the range [1, 10].

The length of accounts[i][j] will be in the range [1, 30].

思路: 很暴力,简单的从头到尾慢慢添加新来的信息。首先,如果该用户在原先的数据库中不存在,则可以直接加入数据库。如果该用户存在与数据库,注意两种情况:

  • 同名, 但没有邮箱重复,说明不是同一个人,直接加入数据库。
  • 同名,且邮箱有重复,说明是同一个人,则把所有关联的邮箱进行合并即可。

代码如下:

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, List<Set<String>>> mem = new HashMap<>();
        int n = accounts.size();
        for (int i = 0; i < n; ++i) {
            List<String> account = accounts.get(i);
            String name = account.get(0);
            if (mem.containsKey(name)) {
                List<Set<String>> mm = mem.get(name);
                int idx = -1;
                Set<String> hh = new HashSet<>();
                for (int k = 1; k < account.size(); ++k){
                    hh.add(account.get(k));
                }
                Set<Integer> mer = new HashSet<>();
                for (int k = 1; k < account.size(); ++k) {
                    String email = account.get(k);
                    for (int j = 0; j < mm.size(); ++j) {
                        if (mm.get(j).contains(email)) {
                            idx = j;
                            mer.add(idx);
                        }
                    }
                }

                if (mer.size() == 0) { // 同名,属于两个人
                    mem.computeIfAbsent(name, k -> new ArrayList<>()).add(hh);
                }
                else { // 属于同一个人
                    // 邮箱合并
                    List<Integer> merge = new ArrayList<>();
                    merge.addAll(mer);

                    mm.get(merge.get(0)).addAll(hh);
                    List<Set<String>> removes = new ArrayList<>();
                    for (int j = 1; j < merge.size(); ++j) {
                        mm.get(merge.get(0)).addAll(mm.get(merge.get(j)));
                        removes.add(mm.get(merge.get(j)));
                    }

                    // 删除之前的邮箱
                    for (Set<String> re : removes) {
                        mm.remove(re);
                    }
                }
            }
            else {
                // 数据库中不存在该用户,直接加入数据库
                Set<String> mails = new HashSet<>();
                for (int j = 1; j < account.size(); ++j) {
                    mails.add(account.get(j));
                }
                mem.computeIfAbsent(name, k -> new ArrayList<>()).add(mails);
            }
        }

        List<List<String>> ans = new ArrayList<>();
        for (String key : mem.keySet()) {
            List<Set<String>> val = mem.get(key);
            for (int i = 0; i < val.size(); ++i) {
                List<String> vv = new ArrayList<>();
                vv.addAll(val.get(i));
                Collections.sort(vv);
                List<String> tmp = new ArrayList<>();
                tmp.add(key);
                tmp.addAll(vv);
                ans.add(tmp);
            }
        }
        return ans;
    }   

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——LinkedList

30512
来自专栏IT可乐

Java 集合详解

一、集合的由来   通常,我们的程序需要根据程序运行时才知道创建多少个对象。但若非程序运行,程序开发阶段,我们根本不知道到底需要多少个数量的对象,甚至不知道它的...

2189
来自专栏Java爬坑系列

【Java入门提高篇】Day27 Java容器类详解(九)LinkedList详解

  这次介绍一下List接口的另一个践行者——LinkedList,这是一位集诸多技能于一身的List接口践行者,可谓十八般武艺,样样精通,栈、队列、双端队列、...

643
来自专栏微信公众号:Java团长

Java 类集框架(Set, List, Map)的使用

Set 接口和 List 接口都是 Collection 的子接口,因此我们先看看Collection 接口中有什么方法:

902
来自专栏Albert陈凯

2018-11-18 swagger2 自动生成API

作者:小莫 链接:https://www.zhihu.com/question/28119576/answer/134580038 来源:知乎 著作权归作...

693
来自专栏移动端开发

Java集合类总结

前言: 这篇准备好好总结一下Java的集合类,在顺便带上Arrays,把这几者之间的关系说清楚,在java.util包中提供了一些集合类,这些集合类又被称作容...

2309
来自专栏一枝花算不算浪漫

Java中常见数据结构List之LinkedList

2755
来自专栏Android机动车

Java 基础(五)——集合源码解析 Set

前面我们学了 List 集合。我们知道 List 是一个有序的集合,可以根据元素的整数索引访问元素,并且允许重复。

811
来自专栏码代码的陈同学

Java基础之你会在foreach遍历集合时进行remove操作吗?

当通过for循环遍历集合时,一般禁止操作(add or remove)集合元素。虽然开发规范里写的非常清楚,但最近还是有人掉坑里导致出了一个小BUG,那我们就一...

1206
来自专栏LanceToBigData

Java常用类(五)之集合工具类Collections

前言    Java提供了一个操作Set、List和Map等集合的工具类:Collections,该工具类提供了大量方法对集合进行排序、查询和修改等操作,   ...

1869

扫码关注云+社区