题目:[1]
给定一个机票的字符串二维数组 [from, to],子数组中的两个成员分别表示飞机出发和降落的机场地点,对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 开始。
输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]
输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]
解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。
抛砖引玉
思路
实现
在枚举路线时,开始的思路是根据起点查到其对应的终点,从前向后遍历这些可能的终点,遇到终点不能作为其他子集起点则跳过最后拼接。
这种思路实现后会发现有些情况会使 tickets 的子集部分不被拼接(及 map 的 value 不能被清空):
枚举路线的逻辑:
递归
终点查询的逻辑借助递归完成
/**
* @param {string[][]} tickets
* @return {string[]}
*/
var findItinerary = function (tickets) {
let _result = [],
len = tickets.length,
map = new Map()
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)
// 枚举 选择传入节点对应的终点
while (items && items.length) {
getEnd(items.shift())
}
// 优先从map-value遍历完成的节点存放
_result.unshift(start)
}
getEnd('JFK')
return _result
}
/**
* @param {string[][]} tickets
* @return {string[]}
*/
var findItinerary = function (tickets) {
let _result = ['JFK'],
len = tickets.length,
map = new Map()
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) {
// 满足能每个子元素都拼接到
if (step === len) return true
let items = map.get(start) || []
// 不存在与当前起点连接的终点
if (items.length === 0) return false
for (let i = 0; i < items.length; i++) {
let item = items[i]
// 一个起点对应多个终点时,如果选择当前起点
items.splice(i, 1)
_result.push(item)
// 检查是否能 - 满足能每个子元素都拼接到
if (getEnd(item, step + 1)) {
return true
} else {
// 如果不满足此时还不能选择这个点与当前起点连接
items.splice(i, 0, item)
_result.pop()
}
}
}
getEnd('JFK', 0)
return _result
}
[1]
题目:: https://leetcode-cn.com/problems/reconstruct-itinerary//