一亩三分地

 找回密码 注册账号

扫描二维码登录本站

微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
查看: 367|回复: 0
收起左侧

[高频题] 亚麻OA最近一道高频新题 "购物模式"

[复制链接] |只看干货 |高频题, 刷题
我的人缘0

升级   53%


分享帖子到朋友圈
zxue | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (14)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
具体题目在这位大佬的帖子里:https://www.1point3acres.com/bbs ... read&tid=672261
找了一下leetcode,发现里面的discuss的链接不work了。自己写了一个,应该是O(VE)的解法。具体思路就是每一个节点走两层BFS,看一下neighbor之间有哎哟有没有相连的。
上面题目帖子里的两个例子都能过。希望大家能一起讨论一下,如果有不对或者可以优化的地方希望大家能指教。谢谢
[Java] 纯文本查看 复制代码
public class Main {

    
    public static int getMinScore(int prod_nodes, int prod_edges, int[] froms, int[] tos) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int n = froms.length;
        for (int i = 0; i < n; i++) {
            int from = froms[i];
            int to = tos[i];
            graph.putIfAbsent(from, new ArrayList<>());
            graph.get(from).add(to);
            graph.putIfAbsent(to, new ArrayList<>());
            graph.get(to).add(from);
        }
        int min = Integer.MAX_VALUE;
    
        for(int node : graph.keySet()) {
            if (graph.get(node).size() < 2) {
                continue;
            }
            List<Integer> neighbors = graph.get(node);
            int node_e = neighbors.size();
            for (int nei : neighbors) {
                int nei_e = graph.get(nei).size();
                for (int nn : graph.get(nei)) {
                    if (neighbors.contains(nn)) {
                        int nn_e = graph.get(nn).size();
                        int cur = (node_e - 2) + (nei_e - 2) + (nn_e - 2);
                        min = Math.min(min, cur);
                    }
                }
            }
        }
        return min == Integer.MAX_VALUE? -1 : min;
    }
    
 
    
    public static void main(String[] args) {
        int pn1 = 6;
        int pe1 = 6;
        int[] froms1 = new int[] {1,2,2,3,4,5};
        int[] tos1 = new int[] {2,4,5,5,5,6};
        System.out.println(getMinScore(pn1, pe1, froms1, tos1));
        int pn2 = 5;
        int pe2 = 6;
        int[] froms2 = new int[] {1,1,2,2,3,4};
        int[] tos2 = new int[] {2,3,3,4,4,5};
        System.out.println(getMinScore(pn2, pe2, froms2, tos2));
    }
}



上一篇:SWE实习面试前,要把非SWE面经也刷了吗?求大佬指点。
下一篇:56题一个语法求解 list.toArray
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

快速回复 返回顶部 返回列表