美文网首页
Order Dependency

Order Dependency

作者: Wenyue_offer | 来源:发表于2017-09-14 08:20 被阅读0次
    import java.util.*;
    class Order{
        String orderName;
        public Order(String orderName)
        {
            this.orderName = orderName;
        }
    }
    class OrderDependency{
        Order order;
        Order dependent;
        public OrderDependency(Order order, Order dependent)
        {
            this.order = order;
            this.dependent = dependent;
        }
    }
    public class Solution {
        public static List<Order> findOrder(List<OrderDependency> depenency)
        {
            Map<String, Integer> inmap = new HashMap<>();
            Map<String, List<String>> outmap = new HashMap<>();
            for(OrderDependency i: depenency)
            {
                if(!inmap.containsKey(i.dependent.orderName)) inmap.put(i.dependent.orderName, 0);
                if(!inmap.containsKey(i.order.orderName)) inmap.put(i.order.orderName, 0);
                inmap.put(i.order.orderName, inmap.get(i.order.orderName) + 1);
                if(!outmap.containsKey(i.dependent.orderName)) outmap.put(i.dependent.orderName, new ArrayList<String>());
                outmap.get(i.dependent.orderName).add(i.order.orderName);
            }
            List<Order> res = new ArrayList<>();
            Queue<String> queue = new LinkedList<>();
            for(String i: inmap.keySet())
            {
                if(inmap.get(i) == 0) queue.offer(i);
            }
            while(!queue.isEmpty())
            {
                String s = queue.poll();
                res.add(new Order(s));
                if(outmap.containsKey(s))
                {
                    for(String o: outmap.get(s))
                    {
                        inmap.put(o, inmap.get(o) - 1);
                        if(inmap.get(o) == 0) queue.offer(o);
                    }
                }
                outmap.remove(s);
            }
            return res;
        }
        public static void main(String[] args)
        {
            List<OrderDependency> input = new ArrayList<>();
            input.add(new OrderDependency(new Order("A"), new Order("E")));
            input.add(new OrderDependency(new Order("D"), new Order("E")));
            input.add(new OrderDependency(new Order("A"), new Order("C")));
            input.add(new OrderDependency(new Order("B"), new Order("D")));
            List<Order> output = findOrder(input);
            for(Order i: output) System.out.print(i.orderName + " ");
        }
    }
    
    

    相关文章

      网友评论

          本文标题: Order Dependency

          本文链接:https://www.haomeiwen.com/subject/pxursxtx.html