Skip to content

Latest commit

 

History

History
154 lines (130 loc) · 4.66 KB

20200827-332.reconstruct-itinerary.md

File metadata and controls

154 lines (130 loc) · 4.66 KB

332.reconstruct-itinerary

题目链接：https://leetcode-cn.com/problems/reconstruct-itinerary/

参考链接：

https://leetcode-cn.com/problems/reconstruct-itinerary/solution/ti-mu-bu-nan-jiu-shi-tu-de-ti-ji-ben-mei-zuo-guo-h/

https://leetcode-cn.com/problems/reconstruct-itinerary/solution/zhong-xin-an-pai-xing-cheng-by-leetcode-solution/

题目

给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。

说明:

  • 如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
  • 所有的机场都用三个大写字母表示（机场代码）。
  • 假定所有机票至少存在一种合理的行程。

示例 1 :

输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]

示例 2 :

输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]
解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。

解题

思路[1]递归回溯

  • 使用对象存储每个地点根据机票生成的连接关系，使用map记录每个机票的数量，使用length记录使用票的数量
  • 根据连接关系，先到达一个地点，使用一张机票，一直到机票使用完，返回结果
  • 如果机票没有使用完几句没有可以到达的节点，则回溯，进行退票
  • 最后返回结果

代码

/**
 * @param {string[][]} tickets
 * @return {string[]}
 */
var findItinerary = function(tickets) {
  const map = new Map()
  const obj = {};
  for(let [from, to] of tickets){
    let tmp = obj[from] || []
    tmp.push(to);
    tmp.sort();
    obj[from] = tmp;
    let value = map.get(`${from}, ${to}`) || 0
    map.set(`${from}, ${to}`, value + 1)
  }
  const ans = []; let length = 0;
  const helper = (from) => {
    // 票用完了
    if(length === tickets.length){
      ans.push(from);
      return true
    }
    let toArr = obj[from];
    if(!toArr || !toArr.length){
      return false
    }
    for(let to of toArr){
      // 没有票了
      let value = map.get(`${from}, ${to}`)
      if(value < 1) {
        continue
      }
      // 设置为去过
      ans.push(from);
      map.set(`${from}, ${to}`, value - 1);
      length++;
      let result = helper(to);
      if(result){
        return true
      }
      // 退票
      ans.pop();
      length--;
      map.set(`${from}, ${to}`, value);
    }
    return false
  }
  helper('JFK')
  return ans
};

思路[2]深度优先遍历

  • 这个的原理在于，对于每个节点，有且最多只有一个分支是死胡同，否则就无法保证至少有一种合理路径，所以我们可以对每个节点的所有边进行深度遍历，走完每个节点的边。将这个节点放到数组中，而最后一个节点一定是死胡同的节点，因为不是死胡同节点的话，他最终还会走回这个节点。
  • 从起点开始进行深度优先遍历
  • 遍历完每个节点之后，删除这条链接
  • 遍历完所有的路径之后，将节点放入结果中

代码

/**
 * @param {string[][]} tickets
 * @return {string[]}
 */
var findItinerary = function(tickets) {
  const graph = getGraph(tickets);
  const ans = []
  dfs(graph,'JFK', ans)
  //深度优先遍历是先进先出，所以reverse反转一下
  return ans.reverse()
};
//从JFS出发，深度优先遍历
function dfs(graph, cur, ans){
  if(!graph.has(cur)) return
  const neighbors = graph.get(cur)
  //题目要求先遍历字典序小的元素
  while(neighbors.length) dfs(graph, neighbors.shift(), ans)
  // 因为深度优先遍历是先进先出，所以每次遍历出发点添加到最后，意为最先出
  ans.push(cur)
}
// 先存储所有机场之间的关系，哪怕tickets中没有给某个机场提供目的地记录，也要把它的目的地置为空数组
function getGraph(tickets){
  const map = new Map()
  //收集每一个出发点的所有目的地
  for(let i = 0;i < tickets.length;i++){
    const from = tickets[i][0]
    const to = tickets[i][1]
    if(!map.has(from)) map.set(from, [])
    if(!map.has(to)) map.set(to, [])
    map.get(from).push(to)
  }
  for(let [key, value] of map){
    //字典顺序排序目的地数组
    value.sort((a, b) => a < b ? -1 : a > b ? 1 : 0)
  }
  return map
}

思考