您好,登录后才能下订单哦!
这篇文章给大家介绍LeetCode - Medium中Reconstruct Itinerary的示例分析,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。
https://leetcode.com/problems/reconstruct-itinerary/
You are given a list of airline tickets
where tickets[i] = [fromi, toi]
represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.
All of the tickets belong to a man who departs from "JFK"
, thus, the itinerary must begin with "JFK"
. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.
For example, the itinerary ["JFK", "LGA"]
has a smaller lexical order than ["JFK", "LGB"]
.
You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.
Example 1:
Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] Output: ["JFK","MUC","LHR","SFO","SJC"]
Example 2:
Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] Output: ["JFK","ATL","JFK","SFO","ATL","SFO"] Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.
Constraints:
1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi
and toi
consist of uppercase English letters.
fromi != toi
一个行程中,如果航班处理不好容易变成一个圈,成为死循环
有多种解法,字母序靠前排在前面,如何该记录映射关系呢 ?
使用回溯法(也可以说深搜) 的话,那么终止条件是什么呢?
搜索的过程中,如何遍历一个机场所对应的所有机场。
对于死循环,举一个有重复机场的例子:
举这个例子是为了说明出发机场和到达机场也会重复的,如果在解题的过程中没有对集合元素处理好,就会死循环。
字母序靠前排在前面,如何该记录映射关系呢 ?
一个机场映射多个机场,机场之间要靠字母序排列,一个机场映射多个机场,可以使用HashMap
,如果让多个机场之间再有顺序的话,就用TreeMap
。
接口Map<String, Map<String, Integer>>
,具体实现类HashMap<String, TreeMap<String, Integer>>
,具体含义Map<出发机场, Map<到达机场, 航班次数>> flight
。
在遍历Map<出发机场, Map<到达机场, 航班次数>> flight
的过程中,使用"航班次数"这个字段的数字做相应的增减,来标记到达机场是否使用过了,避免死锁问题。
如果“航班次数”大于零,说明目的地还可以飞,如果如果“航班次数”等于零说明目的地不能飞了,而不用对集合做删除元素或者增加元素的操作。
回溯算法模板:
void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) { 处理节点; backtracking(路径,选择列表); // 递归 回溯,撤销处理结果 } }
本题以输入:[["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]为例,抽象为树形结构如下:
List<String> path
:路程,也就最终返回结果。
int numOfTickets
:票数,在终止条件处有用。
Map<String, Map<String, Integer>> flight
:具体含义Map<出发机场, Map<到达机场, 航班次数>> flight
。
代码如下:
private boolean backtacking(List<String> path, int startIndex, int numOfTickets, Map<String, Map<String, Integer>> flight) {}
注意函数返回值是boolean,而不是大多数的返回值void。
因为只需要找到一个行程,就是在树形结构中唯一的一条通向叶子节点的路线,便立即返回,如图:
当然本题的flight和path都需要初始化,代码如下:
List<String> path = new ArrayList<>(); Map<String, Map<String, Integer>> flight = ticket2Flight(tickets); path.add("JFK");//加入起始地址 // 用到Java8的流水线和收集器的功能。 private Map<String, Map<String, Integer>> ticket2Flight(List<List<String>> tickets) { return tickets.stream().collect(Collectors.groupingBy(ticket -> ticket.get(0), //groupingBy()的默认实现Map是HashMap Collectors.groupingBy(ticket -> ticket.get(1), TreeMap::new, // Collectors.reducing(0, elem -> 1, Integer::sum)))); }
拿题目中的示例为例,输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] ,这是有4个航班,那么只要找出一种行程,行程里的机场个数是5就可以了。
所以终止条件是:我们回溯遍历的过程中,遇到的机场个数,如果达到了(航班数量+1),那么我们就找到了一个行程,把所有航班串在一起了。
代码如下:
if (path.size() == numOfTickets + 1) { return true; }
直接放码吧!
Map<String, Integer> terminal2NumMap = flight.get(path.get(path.size() - 1)); if (terminal2NumMap != null) { for (Entry<String, Integer> terminal2Num : terminal2NumMap.entrySet()) { if (terminal2Num.getValue() > 0) { terminal2Num.setValue(terminal2Num.getValue() - 1); path.add(terminal2Num.getKey()); if (backtacking(path, numOfTickets, flight)) { return true; } path.remove(path.size() - 1); terminal2Num.setValue(terminal2Num.getValue() + 1); } } }
All the airports are vertices and tickets are directed edges. Then all these tickets form a directed graph.
The graph must be Eulerian since we know that a Eulerian path exists.
Thus, start from "JFK", we can apply the Hierholzer's algorithm to find a Eulerian path in the graph which is a valid reconstruction.
Since the problem asks for lexical order smallest solution, we can put the neighbors in a min-heap. In this way, we always visit the smallest possible neighbor first in our trip.
回溯算法:重新安排行程
Share my solution
import java.util.ArrayList; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Map.Entry; import java.util.PriorityQueue; import java.util.TreeMap; import java.util.stream.Collectors; public class ReconstructItinerary { //方法一:回溯算法 public List<String> findItinerary(List<List<String>> tickets) { List<String> path = new ArrayList<>(); Map<String, Map<String, Integer>> flight = ticket2Flight(tickets); path.add("JFK"); backtacking(path, tickets.size(), flight); return path; } private boolean backtacking(List<String> path, int numOfTickets, Map<String, Map<String, Integer>> flight) { if (path.size() == numOfTickets + 1) { return true; } Map<String, Integer> terminal2NumMap = flight.get(path.get(path.size() - 1)); if (terminal2NumMap != null) { for (Entry<String, Integer> terminal2Num : terminal2NumMap.entrySet()) { if (terminal2Num.getValue() > 0) { terminal2Num.setValue(terminal2Num.getValue() - 1); path.add(terminal2Num.getKey()); if (backtacking(path, numOfTickets, flight)) { return true; } path.remove(path.size() - 1); terminal2Num.setValue(terminal2Num.getValue() + 1); } } } return false; } // Java 8 private Map<String, Map<String, Integer>> ticket2Flight(List<List<String>> tickets) { return tickets.stream().collect(Collectors.groupingBy(ticket -> ticket.get(0), //groupingBy()的默认实现Map是HashMap Collectors.groupingBy(ticket -> ticket.get(1), TreeMap::new, // Collectors.reducing(0, elem -> 1, Integer::sum)))); } //方法二:DFS public List<String> findItinerary2(List<List<String>> tickets) { Map<String, PriorityQueue<String>> flights = new HashMap<>(); List<String> path = new LinkedList<>(); for (List<String> ticket : tickets) { flights.computeIfAbsent(ticket.get(0), k -> new PriorityQueue<>()).add(ticket.get(1)); } dfs("JFK", path, flights); return path; } private void dfs(String departure, List<String> path, Map<String, PriorityQueue<String>> flights) { PriorityQueue<String> arrivals = flights.get(departure); while (arrivals != null && !arrivals.isEmpty()) dfs(arrivals.poll(), path, flights); path.add(0, departure); } }
import static org.hamcrest.CoreMatchers.is; import static org.junit.Assert.*; import static org.springframework.test.util.ReflectionTestUtils.invokeMethod; import java.util.Arrays; import java.util.List; import java.util.Map; import org.junit.Test; public class ReconstructItineraryTest { private ReconstructItinerary obj = new ReconstructItinerary(); private List<List<String>> tickets = Arrays.asList(Arrays.asList("MUC", "LHR"), Arrays.asList("JFK", "MUC"), // Arrays.asList("SFO", "SJC"), Arrays.asList("LHR","SFO")); private List<List<String>> tickets2 = Arrays.asList(Arrays.asList("JFK", "SFO"), Arrays.asList("JFK", "ATL"), // Arrays.asList("SFO", "ATL"), Arrays.asList("ATL","JFK"), Arrays.asList("ATL", "SFO")); private List<List<String>> tickets3 = Arrays.asList(Arrays.asList("JFK","KUL"), Arrays.asList("JFK","NRT"), // Arrays.asList("NRT","JFK")); private List<String> expected = Arrays.asList("JFK", "MUC", "LHR", "SFO", "SJC"); private List<String> expected2 = Arrays.asList("JFK", "ATL", "JFK", "SFO", "ATL", "SFO"); private List<String> expected3 = Arrays.asList("JFK", "NRT", "JFK", "KUL"); @Test public void test() { assertThat(obj.findItinerary(tickets), is(expected)); assertThat(obj.findItinerary(tickets2), is(expected2)); assertThat(obj.findItinerary(tickets3), is(expected3)); } @Test public void test2() { assertThat(obj.findItinerary2(tickets), is(expected)); assertThat(obj.findItinerary2(tickets2), is(expected2)); assertThat(obj.findItinerary2(tickets3), is(expected3)); } @Test public void testTicket2Flight() { Map<String, Map<String, Integer>> ticket2Flight = invokeMethod(obj, "ticket2Flight", tickets); assertEquals("{LHR={SFO=1}, MUC={LHR=1}, SFO={SJC=1}, JFK={MUC=1}}", ticket2Flight.toString()); Map<String, Map<String, Integer>> ticket2Flight2 = invokeMethod(obj, "ticket2Flight", tickets2); assertEquals("{ATL={JFK=1, SFO=1}, SFO={ATL=1}, JFK={ATL=1, SFO=1}}", ticket2Flight2.toString()); } }
关于LeetCode - Medium中Reconstruct Itinerary的示例分析就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。