挨骂总ＯＡ面经

多谢分享。
请问一下这题输入 (a,b), (c,b) 和 (a,b), (b,c) 的返回是一样的么(a, b, c)?

你的union find的算法不太对 我跑了一下case {{“1”，“2”}， {“3”，“4”}，{ “1“， ”3”}}， 其结果应该为 1234， 但是你的算法只得到123， 原因出在这里：
        for(Map.Entry<String, String> ent : unionKeys.entrySet()) {-google 1point3acres
            counts.put(ent.getValue(), counts.getOrDefault(ent.getValue(), 0) + 1);
        }
是不能直接加的 要重复寻找unionkeys的unionkeys的unionkeys的。。。直到key不变为止 具体算法见 https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

据说遥遥领先 发表于 2017-8-24 11:31
请问什么叫做字典顺序最小的？每个朋友圈是一个字符串数组，对于字符串数组如何比较字典顺序？

我感觉他这个答案是当有两个朋友圈数量一样时，比较两个朋友圈里面的字典序最小的人的字典序，我觉得应该是这样

自己写了个比较好理解的版本，供大家参考
static Map<String,String> pre = new HashMap<>();
    public static String[] findLargestFriendCircle(String[][] arr) {
        for(int i = 0; i < arr.length; i ++){
            String m = arr[i][0];
            pre.put(m, m);
            String n = arr[i][1];
            pre.put(n, n);
        }
        for(int i = 0; i < arr.length; i ++){
            String m = arr[i][0];
            String n = arr[i][1];
            String parM = get(m);
            String parN = get(n);
            if(parM.compareTo(parN) < 0){
                pre.put(parM, parN);
            }
            else{
                pre.put(parN, parM);
            }
        }
        Map<String, List<String>> map = new HashMap<>();
        for(String key : pre.keySet()){
            String root = get(key);
            if(map.containsKey(root)){
                map.get(root).add(key);
            }
            else{
                List<String> list = new ArrayList<>();
                list.add(key);
                map.put(root, list);
            }
        }
        int max = 0;
        String maxKey = "";
        for(String str : map.keySet()){
            if(map.get(str).size() > max || map.get(str).size() == max && str.compareTo(maxKey) < 0){
                max = map.get(str).size();
                maxKey = str;
            }
        }
        List<String> list = map.get(maxKey);
        String[] result = new String[list.size()];
        for(int i = 0; i < list.size(); i ++){
            result[i] = list.get(i);
        }
        return result;
    }
    public static String get(String name){
        String root = name;
        while(pre.get(root) != root){
            root = pre.get(root);
        }
        while(pre.get(name) != root){
            String par = pre.get(name);
            pre.put(name, root);
            name = par;
        }
        return root;
    }

顶12楼 - local run 加了这段就能过1234 case了：
        /************************************************************/
        // critical: get final root for each person
        // need this to ensure all people are mapped to "real" root
        for(Map.Entry<String, String> ent : pre.entrySet()) {
                String curVal = ent.getValue();
                String curKey = ent.getKey();
                if (root.containsKey(curVal)) {
                        String finalRoot = find(root, curVal);
                        pre.put(curKey, finalRoot);
                }
        }
        /************************************************************/

waynetang 发表于 2017-9-23 10:01
自己写了个比较好理解的版本，供大家参考
static Map pre = new HashMap();
    public static String[]  ...

谢谢你的solution,  很有启发

不可以给图转成adjacency list之后给所有friend加到一个untraversed set里面，完了一个一个拿出来进行dfs来找出来每个朋友圈的size么？ 之后dfs每traverse到一个friend就给remove from那个untraversed set？

My solution. Ne sure to compress path in union-find. I also used the smallest person's name as representative of a circle.

1. typedef vector<string> VS;
   
2. unordered_map<string, string> rep; // representative of a circle
   
3. 
   
4. string Find(string s) { // find circle representative for s
   
5.     if (!rep.count(s)) rep[s] = s;
   
6.     else if (rep[s] != s) rep[s] = Find(rep[s]);
   
7.     return rep[s];
   
8. }
   
9. 
   
10. void Union(VS& p) { // join cicles of p[0] and p[1]
    
11.     string rep1(Find(p[0])), rep2(Find(p[1]));
    
12.     (rep1 < rep2)? rep[rep2] = rep1 : rep[rep1] = rep2;
    
13. }
    
14. 
    
15. VS largestCircle(vector<VS>& pairs) {   
    
16.     for (auto& p : pairs) Union(p);
    
17.     unordered_map<string, VS> circles;
    
18.     for (auto& p : rep) circles[p.second].push_back(p.first);
    
19.    
    
20.     int maxCircle = 0;
    
21.     string maxRep;
    
22.     for (auto& p : circles)
    
23.         if (p.second.size() > maxCircle ||
    
24.            p.second.size() == maxCircle && p.first < maxRep)
    
25.             maxCircle = p.second.size(), maxRep = p.first;
    
26.     return circles[maxRep];
    
27. }

复制代码

tabletenniser 发表于 2018-1-24 14:43
不可以给图转成adjacency list之后给所有friend加到一个untraversed set里面，完了一个一个拿出来进行dfs来 ...

嗯，我觉得这样也可以，类似于"count number of island"题，但同时要记录每个“island”的大小和最小的名字。