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
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- 图论里面的基础问题。有一堆课程,每个课程都有先后,比如:要上B,就必须先学完A,要上C,又必须先学完B。 输入是D...
- 解題思路 : 就是基本的 BFS 思路 利用 queue 來完成 level order traversal 然後...
- LeetCode 102 Binary Tree Level Order Traversal ==========...
- [广告]分治/递归 思想总结:http://www.jianshu.com/p/6c1de969830c Bina...