LeetCode – Medium – 332. Reconstruct Itinerary

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:

LeetCode - Medium - 332. Reconstruct Itinerary

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

Example 2:

LeetCode - Medium - 332. Reconstruct Itinerary

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

方法一：回溯算法

待解决问题

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

如何理解死循环

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

LeetCode - Medium - 332. Reconstruct Itinerary 举这个例子是为了说明出发机场和到达机场也会重复的，如果在解题的过程中没有对集合元素处理好，就会死循环。

该记录映射关系

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

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

LeetCode - Medium - 332. Reconstruct Itinerary

递归函数参数

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。

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

LeetCode - Medium - 332. Reconstruct Itinerary 当然本题的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.

参考资料

回溯算法：重新安排行程
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());
	}
	
}

展开阅读全文

javaaslist

打赏

0 赞

0 收藏

微信
QQ
微博

作者的其它热门文章

【清华大学】《逻辑学概论》笔记

《Java8实战》笔记（10）：用Optional取代null

Kafka学习笔记

Redis学习笔记

程序员灯塔
转载请注明原文链接：LeetCode – Medium – 332. Reconstruct Itinerary