• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# LeetCode – Medium – 332. Reconstruct Itinerary

6天前 4次浏览

## Topic

• Depth-first Search
• Graph

## Description

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`

## Analysis

### 方法一：回溯算法

#### 待解决问题

1. 一个行程中，如果航班处理不好容易变成一个圈，成为死循环
2. 有多种解法，字母序靠前排在前面，如何该记录映射关系呢 ？
3. 使用回溯法（也可以说深搜） 的话，那么终止条件是什么呢？
4. 搜索的过程中，如何遍历一个机场所对应的所有机场。

#### 回溯三弄

``````void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}

for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
``````

##### 递归函数参数
• `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) {}
``````

``````List<String> path = new ArrayList<>();
Map<String, Map<String, Integer>> flight = ticket2Flight(tickets);

// 用到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))));
}
``````
##### 递归终止条件

``````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);
if (backtacking(path, numOfTickets, flight)) {
return true;
}
path.remove(path.size() - 1);
terminal2Num.setValue(terminal2Num.getValue() + 1);
}
}
}
``````

### 方法二：DFS

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.

### 参考资料

1. 回溯算法：重新安排行程
2. Share my solution

## Submission

``````import java.util.ArrayList;
import java.util.HashMap;
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);
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);
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<>();

for (List<String> ticket : tickets) {
}
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);
}

}
``````

## Test

``````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());
}

}
``````

javaaslist

0

0 收藏

QQ

### 作者的其它热门文章

【清华大学】《逻辑学概论》笔记
《Java8实战》笔记（10）：用Optional取代null
Kafka学习笔记
Redis学习笔记