重新安排行程 | LeetCode- | 回溯算法 |

二分查找你学废了吗？快来看看这道题如何使用二分查找解决吧！

回溯算法练习题

---

LeetCode链接：162. 寻找峰值

---

1.题目描述

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

所有这些机票都属于一个从 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$
• $from_i.length == 3$
• $to_i.length == 3$
• $from_i$和 $to_i$ 由大写英文字母组成
• $from_i \ != to_i$

2.题解

2.1 回溯算法-写法1

• 代码解释：https://leetcode.cn/problems/reconstruct-itinerary/solutions/1/dfshui-su-chao-ji-xiang-xi-jie-shi-by-dr-iy95/

class Solution {
    // 用双端队列存储最终结果，方便在两端进行操作
    public Deque<String> result = new LinkedList<>();

    // 使用 HashMap 存储航班信息，key 为出发机场，value 为到达机场以及相应航班的次数
    // TreeMap 保证到达机场按字典序排列
    public Map<String, Map<String, Integer>> map = new HashMap<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        // 遍历机票信息，构建航班映射表
        for (List<String> t : tickets) {
            Map<String, Integer> temp;
            // 如果出发机场已经存在于 map 中，取出对应的到达机场映射
            if (map.containsKey(t.get(0))) {
                temp = map.get(t.get(0));
                // 更新到达机场的航班次数（允许重复航班）
                temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
            } else {
                // 如果出发机场不存在，创建一个 TreeMap 来保存到达机场，确保按字典序排序
                temp = new TreeMap<>(); // 升序
                temp.put(t.get(1), 1);
            }
            // 将更新后的到达机场映射存回 map
            map.put(t.get(0), temp);
        }

        // 起点是 "JFK"，将其加入结果路径
        result.add("JFK");

        // 开始回溯搜索，尝试找到一条完整的行程
        backtracking(tickets.size());

        // 将结果转换为 List 并返回
        return new ArrayList<>(result);
    }

    // 回溯函数，尝试构建完整行程
    public boolean backtracking(int ticketNum) {
        // 当路径中的节点数等于机票数加 1 时，说明已找到完整路径
        if (result.size() == ticketNum + 1) {
            return true;
        }

        // 获取当前路径最后一个机场
        String last = result.getLast();

        // 检查当前机场是否存在后续航班
        if (map.containsKey(last)) { // 防止空指针异常
            // 遍历所有从该机场出发的航班
            for (Map.Entry<String, Integer> target : map.get(last).entrySet()) {
                int count = target.getValue();
                // 如果还有未使用的航班
                if (count > 0) {
                    // 将该目的地加入结果路径
                    result.add(target.getKey());
                    // 更新该航班的剩余次数
                    target.setValue(count - 1);

                    // 递归调用，继续构建剩余行程
                    if (backtracking(ticketNum)) {
                        return true; // 如果找到可行路径，立即返回
                    }

                    // 回溯操作：移除最后一个添加的目的地，恢复航班次数
                    result.removeLast();
                    target.setValue(count);
                }
            }
        }

        // 如果没有找到有效路径，返回 false
        return false;
    }
}

2.2 回溯算法-写法2-超时

class Solution {
    // 用于存储最终的行程结果
    private LinkedList<String> res;
    // 用于存储当前路径
    private LinkedList<String> path = new LinkedList<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        // 对机票按照目的地字母顺序进行排序，保证字典序最小的行程先被访问
        Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));

        // 起点是 "JFK"，将其加入路径中
        path.add("JFK");

        // 用来标记机票是否已被使用
        boolean[] used = new boolean[tickets.size()];

        // 开始回溯搜索，寻找符合条件的行程
        backTracking((ArrayList) tickets, used);

        // 返回最终结果
        return res;
    }

    // 回溯函数，用来寻找符合条件的行程
    public boolean backTracking(ArrayList<List<String>> tickets, boolean[] used) {
        // 当路径长度等于机票数量 + 1 时，说明找到了完整路径
        if (path.size() == tickets.size() + 1) {
            res = new LinkedList<>(path); // 将当前路径复制到结果中
            return true; // 返回 true 表示已找到结果，终止递归
        }

        // 遍历所有机票，尝试找到下一个符合条件的目的地
        for (int i = 0; i < tickets.size(); i++) {
            // 如果当前机票未被使用，且该机票的出发地与当前路径的最后一个机场相同
            if (!used[i] && tickets.get(i).get(0).equals(path.getLast())) {
                // 将目的地添加到路径中
                path.add(tickets.get(i).get(1));
                // 标记该机票已使用
                used[i] = true;

                // 递归调用，继续寻找下一站行程
                if (backTracking(tickets, used)) {
                    return true; // 如果找到了完整路径，直接返回 true
                }

                // 回溯操作：移除最后一个添加的目的地，并重置该机票的使用状态
                used[i] = false;
                path.removeLast();
            }
        }

        // 如果没有找到有效路径，返回 false
        return false;
    }
}