Topic:[1]
Given a two-dimensional array of ticket strings [from, to], the two members of the subarray represent the departure and landing airport locations of the aircraft, and the itinerary is rearranged.
All of these tickets belonged to a gentleman who left JFK, so the trip had to start at JFK.
instructions
- If multiple trips are available, you can return the smallest combination of trips by character natural ordering. For example, itinerations [“JFK”, “LGA”] are smaller and more prioritized than [“JFK”, “LGB”]
- All airports are represented by three capital letters (airport code).
- Assume that at least one reasonable itinerary exists for all tickets.
The sample
- Example 1
Input: [["MUC"."LHR"], ["JFK"."MUC"], ["SFO"."SJC"], ["LHR"."SFO"]]
Output:"JFK"."MUC"."LHR"."SFO"."SJC"]
Copy the code- Example 2
Input: [["JFK"."SFO"], ["JFK"."ATL"], ["SFO"."ATL"], ["ATL"."JFK"], ["ATL"."SFO"]]
Output:"JFK"."ATL"."JFK"."SFO"."ATL"."SFO"]
Explanation: Another effective trip is ["JFK"."SFO"."ATL"."JFK"."ATL"."SFO"]. But it naturally ranks much larger and lower.
Copy the codeThe topic
Train of thought
- Array tickets, index: 0-> start, 1-> end
- Traverse the group tickets. If the starting and ending points of the two subsets are equal, it means that the two subsets are continuous and can be joined together
- Each subset of tickets is required to have nodes spliced into the result array
- If the same end point corresponds to multiple starting points, join them alphabetically
implementation
- Traversing tickets generates a map, and the starting point is used as the hash of the map: at this time, it involves the problem of repeated starting points, and the problem requires sorting by character size, then the value of the map is stored in the collection of: arrived
- Query the end point corresponding to the starting point from the specified starting point until there is no corresponding end point
When enumerating the route, the initial idea is to find the corresponding end point according to the starting point, and traverse these possible end points from front to back. When the end point cannot be used as the starting point of other subsets, the final splicing is skipped.
After this idea is implemented, we will find that there are some cases where subsets of tickets are not concatenated (and map values cannot be cleared) :
- There are elements that do not connect to other starting points while traversing the map value
- When an endpoint corresponds to multiple starting points, if the starting point with a smaller order is selected, the subsequent nodes will not be connected
Enumeration route logic:
- Recursion to map starts reverse when the value of the map is null (padding from back to front)
- Enumerates multiple starting point recursions, reserving only empty values that can recurse to a map
recursive
The logic of the end-point query is done by recursion
- Parameter: start
- Termination condition: Map has no corresponding starting point
- Recursion to map starts reverse when the value of the map is null (padding from back to front)
/ * *
* @param {string[][]} tickets
* @return {string[]}
* /
var findItinerary = function (tickets) {
let _result = [],
len = tickets.length,
map = new Map(a)
for (let i = 0; i < len; i++) {
if (map.has(tickets[i][0]) {
let items = map.get(tickets[i][0])
items.push(tickets[i][1])
items.sort()
map.set(tickets[i][0], items)
} else {
map.set(tickets[i][0], [tickets[i][1]])
}
}
function getEnd(start) {
let items = map.get(start)
// Enumeration selects the endpoint corresponding to the incoming node
while (items && items.length) {
getEnd(items.shift())
}
// The node on which map-value traversal is completed is stored preferentially
_result.unshift(start)
}
getEnd('JFK')
return _result
}
Copy the code- Enumerates multiple starting point recursions, reserving only empty values that can recurse to a map
/ * *
* @param {string[][]} tickets
* @return {string[]}
* /
var findItinerary = function (tickets) {
let _result = ['JFK'].
len = tickets.length,
map = new Map(a)
for (let i = 0; i < len; i++) {
if (map.has(tickets[i][0]) {
let items = map.get(tickets[i][0])
items.push(tickets[i][1])
items.sort()
map.set(tickets[i][0], items)
} else {
map.set(tickets[i][0], [tickets[i][1]])
}
}
function getEnd(start, step) {
// Satisfy that each child element is concatenated to
if (step === len) return true
let items = map.get(start) || []
// There is no endpoint connected to the current starting point
if (items.length === 0) return false
for (let i = 0; i < items.length; i++) {
let item = items[i]
// If one starting point corresponds to multiple ending points, select the current starting point
items.splice(i, 1)
_result.push(item)
// Check whether each child element can be concatenated to
if (getEnd(item, step + 1)) {
return true
} else {
// If not, you cannot select this point to connect to the current starting point
items.splice(i, 0, item)
_result.pop()
}
}
}
getEnd('JFK'.0)
return _result
}
Copy the codeBlog: Little Bookboy Blog [2]
Every day of the daily problem, write the problem will be synchronized to the public number one day a big Lee column welcome to pay attention to the message
Public number: the little bookboy who pits people
The resources
[1]
Title: : https://leetcode-cn.com/problems/reconstruct-itinerary/
[2]
Bookboy blog: http://gaowenju.com/