KK's blog

每天积累多一些

0%

LeetCode 332 Reconstruct Itinerary

Posted on Edited on Disqus:

LeetCode 332 Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

  1. 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"].
  2. All airports are represented by three capital letters (IATA code).
  3. You may assume all tickets form at least one valid itinerary.

Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

题目大意：

给定一组机票，用出发机场和到达机场[from, to]来表示，重建行程的顺序。所有的机票都属于一个从JFK（肯尼迪国际机场）出发的旅客。因此，行程必须从JFK开始。

注意：

如果存在多重有效的行程，你应当返回字典序最小的那个。例如，行程[“JFK”, “LGA”]的字典序比[“JFK”, “LGB”]要小。
所有的机场用3个大写字母表示（IATA编码）。
你可以假设所有的机票均至少包含一条有效的行程。

解题思路：

这条题实质是记录DFS路径的题目，且对儿子节点的选择是有顺序的。值得注意的是并不是所有路径都是可形成回路，所以需要DFS搜索。
既然是要记录路径就需要用数组保存结果，而有顺序则表示要排序。

  1. 建图，用邻接表来表示HashMap> graph
  2. 对每个节点的邻节点LinkList进行排序
  3. 从JFK开始dfs。1)终止条件为所有ticket都遍历了(达成回路)或者不能够遍历完。2)路径存在数组中。 3)通过删除节点表示已访问DFS该节点后图要恢复成原状态。

注意事项：

  1. 通过删除节点表示已访问DFS该节点后图要恢复成原状态。用下标i来删除，这样才能保证删除再加入仍然有序。另一种方法是用visited边来记录避免修改图。本文用前者
  2. 剪枝： 如果找到结果就返回
  3. 这题只有一条path，不是所有可能性，但让需要用res，复制path到res，因为path会恢复状态。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def findItinerary2(self, tickets: List[List[str]]) -> List[str]:
	graph = collections.defaultdict(list)
	for li in tickets:
		graph[li[0]].append(li[1])
	for li in graph.values():
		li.sort()
	path, res = ['JFK'], []
	self.dfs2(graph, 'JFK', len(tickets), path, res)
	return res[0]

def dfs2(self, graph, start, ticket_left, path, res):
	if ticket_left == 0:
		res.append(list(path)) # remember
		return True
	for i, neighbor in enumerate(graph[start]):
		path.append(neighbor)
		graph[start].pop(i) # remember
		if self.dfs2(graph, neighbor, ticket_left - 1, path, res):
			return True
		graph[start].insert(i, neighbor)
		path.pop()
	return False

注意事项：

  1. 终止条件为所有ticket都遍历了(达成完整路)或者不能够遍历完Dfs API含ticketLeft。如{“JFK”,”KUL”},{“JFK”,”NRT”},{“NRT”,”JFK”}，虽然KUL在NRT前，但KUL不能组成回路。
  2. DFS路径尽量存在数组中，否则用ArrayList中就要先add再remove。
  3. 通过删除节点表示已访问DFS该节点后图要恢复成原状态。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public List<String> findItinerary(String[][] tickets) {
	HashMap<String, LinkedList<String>> graph = new HashMap<String, LinkedList<String>>();
	for(int i=0;i<tickets.length;i++){
		LinkedList<String> neighbor = graph.get(tickets[i][0]);
		if(neighbor==null)
			neighbor = new LinkedList<String>();
		neighbor.add(tickets[i][1]);
		graph.put(tickets[i][0], neighbor);
	}
	Iterator<String> it = graph.keySet().iterator();
	while(it.hasNext()){
		String key = it.next();
		LinkedList<String> neighbor = graph.get(key);
		Collections.sort(neighbor);
		graph.put(key, neighbor);
	}
	String[] re = new String[tickets.length+1];
	String cur = "JFK";
	re[0] = cur;
	isDFS(graph,cur,tickets.length,tickets.length,re);
	return new ArrayList<String>(Arrays.asList(re));
}

public boolean isDFS(HashMap<String, LinkedList<String>> graph, String departCity
		,int ticketLeft, int ticketNum, String[] re){
	if(ticketLeft==0)
		return true;    	
	LinkedList<String> desCity = graph.get(departCity);
	if(desCity==null)
		return false;
	for(int i=0;i<desCity.size();i++){
		String cur = desCity.get(i);
		re[ticketNum-ticketLeft+1] = cur;
		desCity.remove(i);
		graph.put(departCity, desCity);
		if(isDFS(graph,cur,ticketLeft-1,ticketNum,re))
			return true;;
		desCity.add(i,cur);
		graph.put(departCity, desCity);
	}
	return false;
}

算法分析：

时间复杂度为O(n)，空间复杂度O(n)。

Free mock interview