332.重新安排行程

链接：332.重新安排行程
难度：Hard
标签：深度优先搜索、图、欧拉回路
简介：给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。

题解 1 - typescript

• 编辑时间：2020-08-27
• 执行用时：164ms
• 内存消耗：49.1MB
• 编程语言：typescript
• 解法介绍：先进行排序字符，初始化数据，计算机票数量，再深度遍历

function findItinerary(tickets: string[][]): string[] {
  tickets.sort((a, b) => a[1].localeCompare(b[1]));
  class Country {
    to: Country[] = [];
    constructor(public name: string) {}
  }
  const itinerary = new Map<string, number>();
  const format = (from: string, to: string) => `${from}->${to}`;
  const countries: Record<string, Country> = {};
  const isOver = () => !Array.from(itinerary.values()).some(v => v > 0);
  for (const [from, to] of tickets) {
    let fromC = countries[from];
    if (!fromC) countries[from] = fromC = new Country(from);
    let toC = countries[to];
    if (!toC) countries[to] = toC = new Country(to);
    fromC.to.push(toC);
    const formatName = format(from, to);
    const num = itinerary.get(formatName);
    itinerary.set(formatName, num === undefined ? 1 : num + 1);
  }
  const ans: string[][] = [];
  const total: string[] = ['JFK'];
  line('JFK');
  return ans.sort((a, b) => (a.join('') < b.join('') ? -1 : 1))[0];
  function line(countryName: string) {
    // console.log('===');
    // console.log(countryName);
    // console.log(itinerary);
    if (ans.length !== 0) return;
    if (isOver()) {
      ans.push([...total]);
      return;
    }
    const country = countries[countryName];
    for (const c of country.to) {
      const formatName = format(countryName, c.name);
      const num: number = itinerary.get(formatName)!;
      if (num === 0) continue;
      // console.log('---');
      // console.log(formatName);
      // console.log(num);
      // console.log(total);
      itinerary.set(formatName, num - 1);
      total.push(c.name);
      line(c.name);
      total.pop();
      itinerary.set(formatName, num);
    }
  }
}