重新安排行程-回溯算法解法记录

hulingF

2023-12-03

算法

重新安排行程

题目描述：给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

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

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

示例 1：

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

示例 2：

1
2
3

输入：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
from.length == 3
to.length == 3
from 和 to 由大写英文字母组成
from != to

首先对于这个题目，我第一感觉就是回溯法肯定可以解决，回溯法中涉及到去重、组合有序等一般都需要先对输入的数据列表排序，本道题也不例外，因为结果要求是字典排序最小，针对目的地进行排序，这样每次从某个出发点寻找目的地时会优先使用字典序最小的目的地，如果这个目的地走不通会继续往后找字典序靠后的目的地，总归有一个符合的目的地(题目也说明至少存在一条合理的行程路径)。

// 深度遍历过程中的行程路径
LinkedList<String> path = new LinkedList<>();
public List<String> findItinerary(List<List<String>> tickets) {
    // 针对目的地排序
    Collections.sort(tickets, (o1, o2) -> o1.get(1).compareTo(o2.get(1)));
    // 出发点
    path.add("JFK");
    // 深度遍历
    backtracking(tickets, "JFK", new boolean[tickets.size()]);
    return path;
}

private boolean backtracking(List<List<String>> tickets, String address, boolean[] used) {
    // 找到一条合理的行程路径，返回true表明可以停止查找直接返回了
    if (path.size() == used.length + 1) {
        return true;
    }
    for (int i = 0; i < used.length; i++) {
        // 使用过的机票跳过
        if (used[i]) continue;
        // 机票的出发地要跟上一次的目的地相同
        if (tickets.get(i).get(0).equals(address)) {
            // 标记机票使用
            used[i] = true;
            // 添加目的地
            path.add(tickets.get(i).get(1));
            // 继续深度遍历，如果找到则直接返回，不用回溯
            if (backtracking(tickets, tickets.get(i).get(1), used)) return true;
            // 回溯
            path.removeLast();
            used[i] = false;
        }
    }
    return false;
}

这个代码在现在的Leetcode上最后一个测试用例会超时：

回顾我们上面的代码，主要是for循环查找符合的机票（出发地与上一步的目的地相同）比较耗时，需要遍历一遍机票列表，所以我们打算改成使用Map结构加快这一步骤，其中设置的Map<String,Map<String,Integer>>表示《出发地->《目的地->机票数量》》:

// 《出发地->《目的地->机票次数》》
Map<String, Map<String, Integer>> targets = new HashMap<>();
// 深度遍历过程中的行程路径
LinkedList<String> path = new LinkedList<>();
public List<String> findItinerary(List<List<String>> tickets) {
    // 构建Map结构，考虑需要针对目的地排序，因此采用Map<String,TreeMap<String,Integer>>
    for (int i = 0; i < tickets.size(); i++) {
        List<String> ticket = tickets.get(i);
        if (targets.containsKey(ticket.get(0))) {
            Map<String, Integer> map = targets.get(ticket.get(0));
            map.put(ticket.get(1), map.getOrDefault(ticket.get(1), 0) + 1);
        } else {
            Map<String, Integer> map = new TreeMap<>();
            map.put(ticket.get(1), 1);
            targets.put(ticket.get(0), map);
        }
    }
    path.add("JFK");
    backtracking(tickets.size());
    return path;
}

private boolean backtracking(int ticketNum) {
    // 找到一条合理的行程路径，返回true表明可以停止查找直接返回了
    if (path.size() == ticketNum + 1) return true;
    // 如果有连接的后续行程，则遍历可行的后续行程
    if (targets.containsKey(path.getLast())) {
        for (Map.Entry<String, Integer> entry : targets.get(path.getLast()).entrySet()) {
            Integer count = entry.getValue();
            // 机票还有剩余
            if (count > 0) {
                // 机票次数减少
                entry.setValue(count - 1);
                // 添加目的地
                path.add(entry.getKey());
                // 继续深度遍历
                if (backtracking(ticketNum)) return true;
                // 回溯
                path.removeLast();
                entry.setValue(count);
            }
        }
    }
    return false;
}

使用Map除了可以直接定位到给定目的地的符合机票外，还有一个隐藏的好处：避免了多次无用的深度遍历，尤其在同一张机票出现多次的情况下。下面我们举个例子，加入机票列表中存在很多张”JFK”->”AUS”机票，那么我们使用之前第一种方式的时候，遍历机票列表时这些相同的机票肯定是挨着排列的（因为针对目的地对机票列表排序），我们会重复多次尝试”JFK”->”AUS”，但其实尝试一次就可以了，第一次使用”JFK”->”AUS”发现走不通后面挨着的”JFK”->”AUS”其实可以跳过了（我已经尝试过下一步走AUS了，这条路走不通，别让我再尝试了都是一样的结果，难道后面的”AUS”就特殊不成，都是一个目的地罢了），我们采用第二种方式天然符合这个优化特点。

兄弟们，既然我们上面说到了使用Map的重要的隐藏好处就是消除了很多无效的遍历，这其实就是去重啊，我们也可以更新一下我们第一种方式的代码，加上去重逻辑：本层已经使用过一次的目的地不要多次尝试了！

// 深度遍历过程中的行程路径
LinkedList<String> path = new LinkedList<>();
public List<String> findItinerary(List<List<String>> tickets) {
    // 针对目的地排序
    Collections.sort(tickets, (o1, o2) -> o1.get(1).compareTo(o2.get(1)));
    // 出发点
    path.add("JFK");
    // 深度遍历
    backtracking(tickets, "JFK", new boolean[tickets.size()]);
    return path;
}

private boolean backtracking(List<List<String>> tickets, String address, boolean[] used) {
    // 找到一条合理的行程路径，返回true表明可以停止查找直接返回了
    if (path.size() == used.length + 1) {
        return true;
    }
    // 本层遍历过程中上一步使用的目的地，去重需要用到
    String target = "";
    for (int i = 0; i < used.length; i++) {
        // 使用过的机票跳过
        if (used[i]) continue;
        // 机票的出发地要跟上一次的目的地相同，并且消除无效的遍历
        if (tickets.get(i).get(0).equals(address) && !tickets.get(i).get(1).equals(target)) {
            // 记录本层遍历过程中上一次使用的目的地，去重需要使用到
            target = tickets.get(i).get(1);
            // 标记机票使用
            used[i] = true;
            // 添加目的地
            path.add(tickets.get(i).get(1));
            // 继续深度遍历，如果找到则直接返回，不用回溯
            if (backtracking(tickets, tickets.get(i).get(1), used)) return true;
            // 回溯
            path.removeLast();
            used[i] = false;
        }
    }
    return false;
}

真的哭死，一直没有想到这个去重的优化，还是使用第二种方式才提醒了我这个优化点，加上它之后我们一开始的代码就能通过啦！