332. 重新安排行程

给你一份航线列表 tickets ,其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 开始。如果存在多种有效的行程,请你按字典排序返回最小的行程组合。

例如,行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小,排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

示例 1:

1652843430782

输入:tickets = [[“MUC”,“LHR”],[“JFK”,“MUC”],[“SFO”,“SJC”],[“LHR”,“SFO”]]
输出:[“JFK”,“MUC”,“LHR”,“SFO”,“SJC”]

示例2:

1652843463380

输入:tickets = [[“JFK”,“SFO”],[“JFK”,“ATL”],[“SFO”,“ATL”],[“ATL”,“JFK”],[“ATL”,“SFO”]]
输出:[“JFK”,“ATL”,“JFK”,“SFO”,“ATL”,“SFO”]
解释:另一种有效的行程是 [“JFK”,“SFO”,“ATL”,“JFK”,“ATL”,“SFO”] ,但是它字典排序更大更靠后

提示:

  • 1 <= tickets.length <= 300
  • tickets[i].length == 2
  • fromi.length == 3
  • toi.length == 3
  • fromi 和 toi 由大写英文字母组成
  • fromi != toi

算法思路:

采用类似于图的邻接表进行深度优先搜索,在 Java 中可使用 优先队列 PriorityQueue 实现有序,在递归方法中对于传入的 源结点,循环让其后继的结点(有序)出队,并进行递归;为了解决如下特殊情况,考虑先进行递归,最后再用头插法放入结果集中。

1652845717499

代码实现:

public class Q0332ReconstructItinerary {
    public static void main(String[] args) {
        Solution solution = new Q0332ReconstructItinerary().new Solution();
        // String[][] tickets = {{"MUC", "LHR"}, {"JFK", "MUC"}, {"SFO", "SJC"}, {"LHR", "SFO"}};
        // String[][] tickets = {{"JFK", "SFO"}, {"JFK", "ATL"}, {"SFO", "ATL"}, {"ATL", "JFK"}, {"ATL", "SFO"}};
        String[][] tickets = {{"JFK", "KUL"}, {"JFK", "NRT"}, {"NRT", "JFK"}};
        List<List<String>> listList = new ArrayList<>();
        for (String[] ticket : tickets) {
            listList.add(Arrays.asList(ticket));
        }
        List<String> stringList = solution.findItinerary(listList);
        stringList.forEach(System.out::println);
    }

    class Solution {
        public List<String> findItinerary(List<List<String>> tickets) {
            for (List<String> list : tickets) {
                String src = list.get(0);
                String dst = list.get(1);
                if (!map.containsKey(src)) {
                    PriorityQueue<String> pq = new PriorityQueue<>();
                    map.put(src, pq);
                }
                map.get(src).add(dst);
            }
            /*
                NRT:JFK
                JFK:KUL NRT
             */
            dfs("JFK");
            return res;
        }

        private Map<String, PriorityQueue<String>> map = new HashMap<>();
        private List<String> res = new LinkedList<>();

        void dfs(String src) {
            PriorityQueue<String> pq = map.get(src);
            while (pq != null && !pq.isEmpty())
                dfs(pq.poll());
            // 采用头插法
            ((LinkedList<String>) res).addFirst(src);
        }
    }

}

Q.E.D.


以无限为有限,以无法为有法