LeetCode刷题实战332：重新安排行程 / 开普饭

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 重新安排行程，我们先来看题面：

https://leetcode-cn.com/problems/reconstruct-itinerary/

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

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

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

例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票必须都用一次且只能用一次。

示例

解题

思路：

用map记录每一个出发的城市和它能到达的城市，并用pq来给到达的城市从小到大排序

DFS，每次获取当前城市能到达的城市

如果它能到达的城市为空，则把它加入结果

否则遍历它能到达的城市，并对每一个城市DFS

把当前城市加入结果

倒序的结果即为所求

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        HashMap<String, PriorityQueue<String>> map = new HashMap();
        for(List<String> ticket: tickets) {
            if(map.containsKey(ticket.get(0))) {
                map.get(ticket.get(0)).add(ticket.get(1));
            } else {
                PriorityQueue<String> temp = new PriorityQueue<String>();
                temp.add(ticket.get(1));
                map.put(ticket.get(0), temp);
            }
        }
        List<String> result = new ArrayList();
        build("JFK", map, result);
        Collections.reverse(result);
        return result;
    }

    void build(String from, HashMap<String, PriorityQueue<String>> map, List<String> res) {
        PriorityQueue<String> cur = map.get(from);
        while(cur!= null && !cur.isEmpty()) {
            String nfrom = cur.poll();
            build(nfrom, map, res);
        }
        res.add(from);
    }
}