行程Java"/>
重新安排行程Java
给你一份航线列表 tickets ,其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 开始。如果存在多种有效的行程,请你按字典排序返回最小的行程组合。
例如,行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小,排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次
class Solution {private Deque<String> res;private Map<String,Map<String,Integer>> map;private boolean backTracking(int ticketNum){if(res.size()==ticketNum+1){return true;}String last=res.getLast();if(map.containsKey(last)){for(Map.Entry<String,Integer> target:map.get(last).entrySet()){int count=target.getValue();if(count>0){res.add(target.getKey());target.setValue(count-1);if(backTracking(ticketNum)) return true;res.removeLast();target.setValue(count);}}}return false;}public List<String> findItinerary(List<List<String>> tickets) {map=new HashMap<String,Map<String,Integer>>();res=new LinkedList<>();for(List<String>t:tickets){Map<String,Integer> temp;if(map.containsKey(t.get(0))){temp=map.get(t.get(0));temp.put(t.get(1),temp.getOrDefault(t.get(1),0)+1);}else{temp=new TreeMap<>();temp.put(t.get(1),1);}map.put(t.get(0),temp);}res.add("JFK");backTracking(tickets.size());return new ArrayList<>(res);}
}
我自己用IDEA跑了一下,结果更容易理解代码的循环是如何进行的
更多推荐
重新安排行程Java
发布评论