Shulou(Shulou.com)06/03 Report--

This article introduces the example analysis of Reconstruct Itinerary in LeetCode-Medium. The content is very detailed. Interested friends can use it for reference. I hope it will be helpful to you.

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 ticket.get (1), TreeMap::new, / / Collectors.reducing (0, elem-> 1, Integer::sum));} Recursive termination condition

Take the example in the title as an example, enter: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]], there are four flights, so as long as you find a kind of itinerary, the number of airports in the itinerary is 5.

So the termination condition is: in the process of traversing, we encounter the number of airports, if we reach (the number of flights + 1), then we find a schedule and string all the flights together.

The code is as follows:

If (path.size ()) = = numOfTickets + 1) {return true;} Logic of single-layer search

Just put it in the code!

Map terminal2NumMap = flight.get (path.get (path.size ()-1)); if (terminal2NumMap! = null) {for (Entry 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);}} method 2: 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 an Eulerian path exists.

Thus, start from "JFK", we can apply the Hierholzer's algorithm to find an 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.

references

Backtracking algorithm: rescheduling

Share my solution

Submissionimport 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 {/ / method 1: backtracking algorithm public List findItinerary (List tickets) {List path = new ArrayList (); Map flight = ticket2Flight (tickets) Path.add ("JFK"); backtacking (path, tickets.size (), flight); return path;} private boolean backtacking (List path, int numOfTickets, Map flight) {if (path.size () = = numOfTickets + 1) {return true } Map terminal2NumMap = flight.get (path.get (path.size ()-1)) If (terminal2NumMap! = null) {for (Entry 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 ticket2Flight (List tickets) {return tickets.stream () .collect (Collectors.groupingBy (ticket-> ticket.get (0), / / groupingBy () default implementation Map is HashMap Collectors.groupingBy (ticket-> ticket.get (1), TreeMap::new) / / Collectors.reducing (0, elem-> 1, Integer::sum) Method 2: DFS public List findItinerary2 (List tickets) {Map flights = new HashMap (); List path = new LinkedList (); for (List 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 path, Map flights) {PriorityQueue arrivals = flights.get (departure); while (arrivals! = null & &! arrivals.isEmpty () dfs (arrivals.poll (), path, flights) Path.add (0, departure);}} Testimport 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 tickets = Arrays.asList (Arrays.asList ("MUC", "LHR"), Arrays.asList ("JFK", "MUC"), / / Arrays.asList ("SFO", "SJC"), Arrays.asList ("LHR", "SFO")) Private List 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 tickets3 = Arrays.asList (Arrays.asList ("JFK", "KUL"), Arrays.asList ("JFK", "NRT"), / / Arrays.asList ("NRT", "JFK")) Private List expected = Arrays.asList ("JFK", "MUC", "LHR", "SFO", "SJC"); private List expected2 = Arrays.asList ("JFK", "ATL", "JFK", "SFO", "ATL", "SFO"); private List 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 ticket2Flight = invokeMethod (obj, "ticket2Flight", tickets); assertEquals ("{LHR= {SFO=1}, MUC= {LHR=1}, SFO= {SJC=1}, JFK= {MUC=1}}", ticket2Flight.toString ()); Map ticket2Flight2 = invokeMethod (obj, "ticket2Flight", tickets2) AssertEquals ("{ATL= {JFK=1, SFO=1}, SFO= {ATL=1}, JFK= {ATL=1, SFO=1}}", ticket2Flight2.toString ());}} this is the end of the sample analysis of Reconstruct Itinerary in LeetCode-Medium. I hope the above content can be helpful to you and learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.