LeetCode - Medium - 332. Reconstruct Itinerary

男娘i 2022-11-16 00:57 163阅读 0赞

## Topic ##

*  Depth-first Search
 *  Graph

## Description ##

[https://leetcode.com/problems/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:**

![d27795b8048350330fbf0beca65c3f41.png][]

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
    Output: ["JFK","MUC","LHR","SFO","SJC"]

**Example 2:**

![c44a28217edd49aba63e72abcba06879.png][]

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.  搜索的过程中，如何遍历一个机场所对应的所有机场。

#### 如何理解死循环 ####

对于死循环，举一个有重复机场的例子：

![5baa26b149e8f1586441f2b323ade465.png][]  
举这个例子是为了说明出发机场和到达机场也会重复的，**如果在解题的过程中没有对集合元素处理好，就会死循环。**

#### 该记录映射关系 ####

字母序靠前排在前面，如何该记录映射关系呢 ？

一个机场映射多个机场，机场之间要靠字母序排列，一个机场映射多个机场，可以使用`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”\]为例，抽象为树形结构如下：

![efe4ec4d7f6fc5b7175eb970f6b00a69.png][]

##### 递归函数参数 #####

*  `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。

因为只需要找到一个行程，就是在树形结构中唯一的一条通向叶子节点的路线，便立即返回，如图：

![efe4ec4d7f6fc5b7175eb970f6b00a69.png][]  
当然本题的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);
    		}
    	}
    }

### 方法二：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.  [回溯算法：重新安排行程][Link 1]
2.  [Share my solution][]

## Submission ##

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

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

[https_leetcode.com_problems_reconstruct-itinerary]: https://leetcode.com/problems/reconstruct-itinerary/
[d27795b8048350330fbf0beca65c3f41.png]: /images/20221022/4f171e3cf3d5406c981479d1c87b9469.png
[c44a28217edd49aba63e72abcba06879.png]: /images/20221022/4b6b46d4d58f4ee4866c8e10088cdb58.png
[5baa26b149e8f1586441f2b323ade465.png]: /images/20221022/c22b3a68ed044af6a583e285bbc74de0.png
[efe4ec4d7f6fc5b7175eb970f6b00a69.png]: /images/20221022/4df51386e8d14f32a23b63aa3c93b117.png
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247485596&idx=1&sn=4a6ab3905fb1076cbb7f78673ef8afad&scene=21#wechat_redirect
[Share my solution]: https://leetcode.com/problems/reconstruct-itinerary/discuss/78766/Share-my-solution