欧美一区二区三区老妇人-欧美做爰猛烈大尺度电-99久久夜色精品国产亚洲a-亚洲福利视频一区二区

LeetCode-Medium中ReconstructItinerary的示例分析

這篇文章給大家介紹LeetCode - Medium中Reconstruct Itinerary的示例分析，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

創(chuàng)新互聯(lián)是一家專注于成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)與策劃設(shè)計(jì),漢陰網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)十多年,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:漢陰等地區(qū)。漢陰做網(wǎng)站價(jià)格咨詢:028-86922220

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中Reconstruct Itinerary的示例分析

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

Example 2:

LeetCode - Medium中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

方法一：回溯算法

待解決問題

  1. 一個(gè)行程中，如果航班處理不好容易變成一個(gè)圈，成為死循環(huán)

  2. 有多種解法，字母序靠前排在前面，如何該記錄映射關(guān)系呢 ？

  3. 使用回溯法（也可以說深搜） 的話，那么終止條件是什么呢？

  4. 搜索的過程中，如何遍歷一個(gè)機(jī)場所對應(yīng)的所有機(jī)場。

如何理解死循環(huán)

對于死循環(huán)，舉一個(gè)有重復(fù)機(jī)場的例子：

LeetCode - Medium中Reconstruct Itinerary的示例分析 舉這個(gè)例子是為了說明出發(fā)機(jī)場和到達(dá)機(jī)場也會重復(fù)的，如果在解題的過程中沒有對集合元素處理好，就會死循環(huán)。

該記錄映射關(guān)系

字母序靠前排在前面，如何該記錄映射關(guān)系呢 ？

一個(gè)機(jī)場映射多個(gè)機(jī)場，機(jī)場之間要靠字母序排列，一個(gè)機(jī)場映射多個(gè)機(jī)場，可以使用HashMap，如果讓多個(gè)機(jī)場之間再有順序的話，就用TreeMap。

接口Map<String, Map<String, Integer>>，具體實(shí)現(xiàn)類HashMap<String, TreeMap<String, Integer>>，具體含義Map<出發(fā)機(jī)場, Map<到達(dá)機(jī)場, 航班次數(shù)>> flight。

在遍歷Map<出發(fā)機(jī)場, Map<到達(dá)機(jī)場, 航班次數(shù)>> flight的過程中，使用"航班次數(shù)"這個(gè)字段的數(shù)字做相應(yīng)的增減，來標(biāo)記到達(dá)機(jī)場是否使用過了，避免死鎖問題。

如果“航班次數(shù)”大于零，說明目的地還可以飛，如果如果“航班次數(shù)”等于零說明目的地不能飛了，而不用對集合做刪除元素或者增加元素的操作。

回溯三弄

回溯算法模板：

void backtracking(參數(shù)) {
    if (終止條件) {
        存放結(jié)果;
        return;
    }

    for (選擇：本層集合中元素（樹中節(jié)點(diǎn)孩子的數(shù)量就是集合的大小）) {
        處理節(jié)點(diǎn);
        backtracking(路徑，選擇列表); // 遞歸
        回溯，撤銷處理結(jié)果
    }
}

本題以輸入：[["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]為例，抽象為樹形結(jié)構(gòu)如下：

LeetCode - Medium中Reconstruct Itinerary的示例分析

遞歸函數(shù)參數(shù)

  • List<String> path：路程，也就最終返回結(jié)果。

  • int numOfTickets：票數(shù)，在終止條件處有用。

  • Map<String, Map<String, Integer>> flight：具體含義Map<出發(fā)機(jī)場, Map<到達(dá)機(jī)場, 航班次數(shù)>> flight。

代碼如下：

private boolean backtacking(List<String> path, int startIndex, int numOfTickets, Map<String, Map<String, Integer>> flight) {}

注意函數(shù)返回值是boolean，而不是大多數(shù)的返回值void。

因?yàn)橹恍枰业揭粋€(gè)行程，就是在樹形結(jié)構(gòu)中唯一的一條通向葉子節(jié)點(diǎn)的路線，便立即返回，如圖：

LeetCode - Medium中Reconstruct Itinerary的示例分析 當(dāng)然本題的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()的默認(rèn)實(shí)現(xiàn)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個(gè)航班，那么只要找出一種行程，行程里的機(jī)場個(gè)數(shù)是5就可以了。

所以終止條件是：我們回溯遍歷的過程中，遇到的機(jī)場個(gè)數(shù)，如果達(dá)到了（航班數(shù)量+1），那么我們就找到了一個(gè)行程，把所有航班串在一起了。

代碼如下：

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. 回溯算法：重新安排行程

  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()的默認(rèn)實(shí)現(xiàn)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());
	}
	
}

關(guān)于LeetCode - Medium中Reconstruct Itinerary的示例分析就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。

分享標(biāo)題：LeetCode-Medium中ReconstructItinerary的示例分析
本文路徑：http://www.chinadenli.net/article26/pgccjg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信公眾號、軟件開發(fā)、網(wǎng)站收錄、關(guān)鍵詞優(yōu)化、Google、服務(wù)器托管

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

外貿(mào)網(wǎng)站建設(shè)