LeetCode算法题解（回溯、难点）|LeetCode332. 重新安排行程

LeetCode332. 重新安排行程

题目链接：332. 重新安排行程

题目描述：

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

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

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

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

示例 1：

输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

示例 2：

输入：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

`算法分析：`

首先我们可以通过建立一张嵌套的哈希表来记录出发机场和降落机场的映射关系（注意相同的机票可能会出现多张，所以我们也要记录航班的次数）。

Map<String, Map<String, Integer>>map;//Map<出发机场，Map<到达机场，航班次数>>

对map的初始化的代码如下：

map = new HashMap<String, Map<String, Integer>>();
for(List<String> t : tickets) {//将每张机票放入到map的对应关系当中
     Map<String, Integer>tem;
     if(map.containsKey(t.get(0))) {
        tem = map.get(t.get(0));
        tem.put(t.get(1), tem.getOrDefault(t.get(1), 0) + 1);
     }else {
        tem = new TreeMap<>();
        tem.put(t.get(1), 1);
     }
     map.put(t.get(0), tem);
}

然后通过回溯遍历行程，这里要明白行程path中走过的机场次数等于机票数加一。（如示例1的机票数是[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]，4张，那么行程中所经过的机场数就是5，["JFK","ATL","JFK","SFO","ATL","SFO"]）。

所以回溯结束的条件就是当行程（path）的长度等于机票数加一（此时每张机票都用完了），我们返回一个布尔类型true，标记找到合理的行程了。

public boolean backTravel(int num) {
        if(path.size() == num + 1) return true;
}

回溯当中的单层搜索逻辑（遍历一个出发机场对应的所有到达机场）。

遍历过程如下：

String last = path.getLast();//记录当前行程中最后一个机场，当作出发的机场
        if(map.containsKey(last)) {//如果有对应的到达机场，遍历所有的到达机场
            for(Map.Entry<String, Integer>tem : map.get(last).entrySet()) {
                int count = tem.getValue();
                if(count > 0) {//如果航班次数大于0 ，说明还有机票
                    path.add(tem.getKey());//将到达机场放入行程
                    tem.setValue(count - 1);//航班次数-1
                    if(backTravel(num)) return true;//递归，如果递归结果为true，说明已经找到一个合理的形成了，不必在遍历，返回true
                    //回溯
                    path.removeLast();
                    tem.setValue(count);
                }
            }
        }

完整的代码如下：

class Solution {
    LinkedList<String>path;//用来记录合理的行程
    Map<String, Map<String, Integer>>map;//用来记录每张机票是否用过
    //Map<出发机场，Map<到达机场，航班次数>>
    public boolean backTravel(int num) {
        if(path.size() == num + 1) return true;//如果行程的机场数是票数加一，那么说明每一张机票肯定都用完了，返回标记true。
        String last = path.getLast();//记录当前行程中最后一个机场，当作出发的机场
        if(map.containsKey(last)) {//如果有对应的到达机场，遍历所有的到达机场
            for(Map.Entry<String, Integer>tem : map.get(last).entrySet()) {
                int count = tem.getValue();
                if(count > 0) {//如果航班次数大于0 ，说明还有机票
                    path.add(tem.getKey());//将到达机场放入行程
                    tem.setValue(count - 1);//航班次数-1
                    if(backTravel(num)) return true;//递归，如果递归结果为true，说明已经找到一个合理的形成了，不必在遍历，返回true
                    //回溯
                    path.removeLast();
                    tem.setValue(count);
                }
            }
        }
        return false;
    }
    public List<String> findItinerary(List<List<String>> tickets) {
        map = new HashMap<String, Map<String, Integer>>();
        path = new LinkedList<>();
        for(List<String> t : tickets) {//将每张机票放入到map的对应关系当中
            Map<String, Integer>tem;
            if(map.containsKey(t.get(0))) {
                tem = map.get(t.get(0));
                tem.put(t.get(1), tem.getOrDefault(t.get(1), 0) + 1);
            }else {
                tem = new TreeMap<>();
                tem.put(t.get(1), 1);
            }
            map.put(t.get(0), tem);
        }
        path.add("JFK");//将出发的机场首先插入到行程当中
        backTravel(tickets.size());
        return (List)path;

    }
}