技术控

    今日:136| 主题:49552
收藏本版 (1)
最新软件应用技术尽在掌握

[其他] 【Amazon-OA2面经】城市连接问题,即MST

[复制链接]
不明觉厉 发表于 2016-10-3 18:53:16
189 12

立即注册CoLaBug.com会员,免费获得投稿人的专业资料,享用更多功能,玩转个人品牌!

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

x
题目内容

    在写这一篇的时候,这题非常出名,因为16年秋首批爆出的video第三题都是这道。做出来的就能拿到video,价值108k+18k美刀至少,比摸金校尉三人合体都多,做不出来也能免费去西雅图来一圈儿,吃喝减半住宿全免,但群面通过率远低于video,所以为了生存这道题必须跑出来。
    题目内容是这样的,给十几个城市供电,连接不同城市的花费不同,让花费最小同时连到所有的边。给出一系列connection类,里面是edge两端的城市名和它们之间的一个cost,找出要你挑一些边,把所有城市连接起来并且总花费最小。不能有环,最后所以城市要连成一个连通块。
    不能的话输出空表,最后还要按城市名字排序输出,按照node1来排序,如果一样的话再排node2。
    输入:
    {"Acity","Bcity",1}
    ("Acity","Ccity",2}
    ("Bcity","Ccity",3}
    输出:
    ("Acity","Bcity",1}
    ("Acity","Ccity",2}
    补充一句,test case一共有6个。
    解决思路

    思路会有很多,我的想法是Kruskal+Union Find,将输入的一群connection类(其实就是边)按照cost从小到大排序(Kruskal算法),然后遍历。挑出一个connection之后,看一下edge两头的城市属于哪一个团伙(Union Find)。如果落单了就加入,不同团伙就合并,都是落单了就抱团。
    最后有两个要求,1.如果MST不存在,那么输出一个空表(应该不是null)。这个可以用union find思想,最后查有几个union,如果大家都是自己人,那么就正常输出,如果大家是1,有零星2了,那就空表了。2.输出要按照城市的名字排序,这个不难,就正常排序就行。
    code

  1. //给好的connection class,两个城市名,和一个cost。
  2. import java.util.*; //这句话极度重要
  3. class Connection{
  4.     String node1;
  5.     String node2;
  6.     int cost;
  7.     public Connection(String a, String b, int c){
  8.         node1 = a;
  9.         node2 = b;
  10.         cost = c;
  11.     }
  12. }
  13. //下面进入正题
  14. public class City_Connections {
  15. private static int unionNum;//这里开个全局变量,不丢人。
  16. //这个static是题目要求的,我自己一般不写,累。
  17. public static ArrayList<Connection> getLowCost(ArrayList<Connection> connections){
  18.     //先把空的情形挡掉
  19.     if (connections == null || connections.size() == 0){
  20.         return new ArrayList<>();
  21.     }
  22.     ArrayList<Connection> result = new ArrayList<>();
  23.     Map<String, Integer> map = new HashMap<>();
  24.     //这里把cost小的往前排。
  25.     Collections.sort(connections, new Comparator<Connection>() {
  26.         @Override
  27.         public int compare(Connection o1, Connection o2) {
  28.             return o1.cost - o2.cost;
  29.         }
  30.     });
  31.     unionNum = 0;
  32.     for (Connection c : connections){
  33.         String a = c.node1;
  34.         String b = c.node2;
  35.         //看城市是不是连过了,要是可以连,那么就在result里面加上
  36.         if (union(map, a, b)){
  37.             result.add(c);
  38.         }
  39.     }
  40.     //这里要检查一下,是不是所有的城市都属于同一个union
  41.     String find = connections.get(0).node1;
  42.     int union = map.get(find);
  43.     for (String str : map.keySet()){
  44.         // 如果我们中出了一个叛徒,返回空表
  45.         if (map.get(str) != union){
  46.             return new ArrayList<>();
  47.         }
  48.     }
  49.     //这里最后要求按照城市的名字排序
  50.     Collections.sort(result, new Comparator<Connection>() {
  51.         @Override
  52.         public int compare(Connection o1, Connection o2) {
  53.             if(o1.node1.equals(o2.node1)){
  54.                 return o1.node2.compareTo(o2.node2);
  55.             }
  56.             return o1.node1.compareTo(o2.node1);
  57.         }
  58.     });
  59.     return result;
  60. }
  61. private static boolean union(Map<String, Integer> map, String a, String b){
  62.     if (!map.containsKey(a) && !map.containsKey(b)){
  63.         map.put(a, unionNum);
  64.         map.put(b, unionNum);
  65.         //这里用了一个新的没用过的数字
  66.         unionNum++;
  67.         return true;
  68.     }
  69.     //只有一方落单,那就加入有组织的一方
  70.     if (map.containsKey(a) && !map.containsKey(b)){
  71.         int aU = map.get(a);
  72.         map.put(b, aU);
  73.         return true;
  74.     }
  75.     if (!map.containsKey(a) && map.containsKey(b)){
  76.         int bU = map.get(b);
  77.         map.put(a, bU);
  78.         return true;
  79.     }
  80.     //两个人都有团伙的情况。
  81.     int aU = map.get(a);
  82.     int bU = map.get(b);
  83.     //如果是自己人,那肯定要踢掉,否则成环了
  84.     if(aU == bU) return false;
  85.     //把所有对方的团伙都吃进来
  86.     for (String s : map.keySet()) {
  87.         if (map.get(s) == bU) map.put(s, aU);
  88.     }
  89.     return true;
  90. }
  91. public static void main(String[] args) {
  92.     ArrayList<Connection> connections = new ArrayList<>();
  93.     //下面的图是个苯环,中间加上了几根,如果想验证空表,去掉几根线就行。
  94.     connections.add(new Connection("A","B",6));
  95.     connections.add(new Connection("B","C",4));
  96.     connections.add(new Connection("C","D",5));
  97.     connections.add(new Connection("D","E",8));
  98.     connections.add(new Connection("E","F",2));
  99.     connections.add(new Connection("B","F",10));
  100.     connections.add(new Connection("E","C",9));
  101.     connections.add(new Connection("F","C",7));
  102.     connections.add(new Connection("B","E",3));
  103.     connections.add(new Connection("A","F",16));
  104.     //这里就输出一下看看结果。
  105.     ArrayList<Connection> res = getLowCost(connections);
  106.     for (Connection c : res){
  107.         System.out.println(c.node1 + " -> " + c.node2 + " " + c.cost);
  108.     }
  109. }
复制代码
}
  复杂度分析

  OA里面的题复杂度就不管了,能跑出来就行。重点关注test case不通过的情况。不过这个复杂度还是O(ElogE)吧,因为有次对所有E(Edge)的排序,算是大头,其他的操作没有比这个多的了。test case只想出孤立两个城市,就是一根connection。如果在connections表里面有个从未出现过的城市,比如铁岭(A-B,C-D,铁岭,法库),那我是真的没有办法了。
  最后再说两句

    当年二战,日本偷袭珍珠港的时候,成功的信号是『虎!虎!虎!』。这次OA成功的信号就是『威丢!威丢!威丢!』
    如有问题,恳请指出,一经采纳,我把冰箱里速冻的馒头亲手热给你,毕竟这是我目前身上最值钱的东西了。
友荐云推荐




上一篇:在 Laravel 5 中使用 Laravel Excel 实现 Excel/CSV 文件导入导出功能
下一篇:zabbix基础知识
酷辣虫提示酷辣虫禁止发表任何与中华人民共和国法律有抵触的内容!所有内容由用户发布,并不代表酷辣虫的观点,酷辣虫无法对用户发布内容真实性提供任何的保证,请自行验证并承担风险与后果。如您有版权、违规等问题,请通过"联系我们"或"违规举报"告知我们处理。

纸飞机的春天 发表于 2016-10-4 06:21:38
佩服佩服!
回复 支持 反对

使用道具 举报

南平1号 发表于 2016-10-9 20:11:59
谢谢不明觉厉的分享!
回复 支持 反对

使用道具 举报

烟火的懦弱 发表于 2016-10-19 05:04:43
这么经典的话只有不明觉厉能想到!
回复 支持 反对

使用道具 举报

Towardset 发表于 2016-10-19 06:32:51
兰州烧饼,鉴定完毕!
回复 支持 反对

使用道具 举报

qijiworld20140 发表于 2016-10-19 19:03:23
报告!我就是路过来看看的。。。
回复 支持 反对

使用道具 举报

张远强 发表于 2016-10-20 01:13:49
鄙视楼下的顶帖没我快,哈哈
回复 支持 反对

使用道具 举报

戴世发 发表于 2016-10-20 03:23:50
谁抢沙发???
回复 支持 反对

使用道具 举报

xundoucha 发表于 2016-10-20 09:38:24
我唯一的缺点就是钱多,而现在我几乎完美了。
回复 支持 反对

使用道具 举报

hr2355 发表于 2016-10-25 13:35:37
学习下
回复 支持 反对

使用道具 举报

*滑动验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

我要投稿

推荐阅读

扫码访问 @iTTTTT瑞翔 的微博
回页顶回复上一篇下一篇回列表手机版
手机版/CoLaBug.com ( 粤ICP备05003221号 | 文网文[2010]257号 )|网站地图 酷辣虫

© 2001-2016 Comsenz Inc. Design: Dean. DiscuzFans.

返回顶部 返回列表