leetCode-332:Reconstruct Itinerary

问题描述

给定一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。要求对该行程进行重新规划排序（一笔画的做法）。该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

样例输入输出

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

输出：[“JFK”,”MUC”,”LHR”,”SFO”,”SJC”]

解释：tickets代表的图如下

输入：tickets = [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]]

输出：[“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”]

解释：tickets代表的图如下

问题解法

此题是需要将行程按一笔画的方式重新给出每个节点的顺序，使用 Hierholzer 算法进行求解即可，参考：https://leetcode.cn/problems/reconstruct-itinerary/solutions/389885/zhong-xin-an-pai-xing-cheng-by-leetcode-solution。`Hierholzer ` 算法流程如下

从起点出发，进行深度优先搜索。

每次沿着某条边从某个顶点移动到另外一个顶点的时候，都需要删除这条边。

如果没有可移动的路径，则将所在节点加入到栈中，并返回。

如果要顺序输出路径，则需要将栈中存储的节点进行逆序排序后输出

代码如下

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, Queue<String>> map = buildMap(tickets);
        List<String> result = new ArrayList<>();
        search(map, result, "JFK");
        Collections.reverse(result);
        return result;
    }

    private void search(Map<String, Queue<String>> map, List<String> result, String current) {
        Queue<String> queue = map.get(current);
        if (queue != null) {
            while (!queue.isEmpty()) {
                search(map, result, queue.poll());
            }
        }

        result.add(current);
    }

    private Map<String, Queue<String>> buildMap(List<List<String>> tickets) {
        Map<String, Queue<String>> map = new HashMap<>();
        for (List<String> ticket : tickets) {
            String from = ticket.get(0);
            String to = ticket.get(1);
            map.putIfAbsent(from, new PriorityQueue<>());
            map.get(from).add(to);
        }

        return map;
    }
}

参考资料

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