当前位置：首页 > news >正文

LeetCode题练习与总结：重新安排行程--332

news 2024/10/23 16:30:35

一、题目描述

给你一份航线列表 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来存储每个出发机场到其目的机场列表的映射。为了方便按字典序排序，我们将目的机场列表存储在一个优先队列（最小堆）中。
从JFK出发，我们使用深度优先搜索（DFS）来探索所有可能的路径。
由于我们要求字典序最小的路径，所以每次从当前机场出发时，我们都优先选择字典序最小的机场。
在搜索过程中，当我们使用了一张机票后，我们需要将其从优先队列中移除，以防止重复使用。
当我们使用完所有机票时，我们就找到了一条有效的路径。由于题目保证至少存在一种合理的行程，所以我们的DFS一定能找到解。
最后，我们将找到的路径反转，得到最终的行程。

三、具体代码

import java.util.*;class Solution {public List<String> findItinerary(List<List<String>> tickets) {// 使用Map存储每个出发机场到其目的机场列表的映射Map<String, PriorityQueue<String>> map = new HashMap<>();for (List<String> ticket : tickets) {map.putIfAbsent(ticket.get(0), new PriorityQueue<>());map.get(ticket.get(0)).offer(ticket.get(1));}// 存储最终的行程List<String> itinerary = new ArrayList<>();// 从JFK出发进行DFSdfs("JFK", map, itinerary);// 反转行程列表Collections.reverse(itinerary);return itinerary;}private void dfs(String from, Map<String, PriorityQueue<String>> map, List<String> itinerary) {// 获取当前机场的目的机场列表PriorityQueue<String> dests = map.get(from);// 当目的机场列表为空时，说明已经使用完所有机票，将当前机场添加到行程while (dests != null && !dests.isEmpty()) {// 取出字典序最小的机场String to = dests.poll();dfs(to, map, itinerary);}// 将当前机场添加到行程（由于是从叶子节点开始添加，所以最终需要反转行程）itinerary.add(from);}
}

在这段代码中，我们首先创建了一个映射，将每个出发机场映射到一个优先队列，其中包含所有可能的目的机场。然后，我们从JFK开始进行深度优先搜索，每次都选择字典序最小的目的地。搜索完成后，我们将得到的行程反转，以得到正确的顺序。

四、时间复杂度和空间复杂度

1. 时间复杂度

构建映射（Map）的时间复杂度：
- 遍历所有的机票列表 tickets，其大小为 n。
- 对于每张机票，我们将其出发机场作为键插入到映射中，如果键不存在则创建一个新的优先队列（PriorityQueue），这是一个 O(1) 的操作。
- 将目的机场插入到对应的优先队列中，插入操作的时间复杂度为 O(log k)，其中 k 是该出发机场对应的目的机场数量。
- 因此，构建映射的总时间复杂度为 O(n log k)。
深度优先搜索（DFS）的时间复杂度：
- 在最坏情况下，我们可能需要访问所有的机票，即每个机票都会被访问一次。
- 对于每张机票，我们都会执行一次 poll 操作来取出字典序最小的机场，这同样是 O(log k) 的操作。
- 因此，DFS 的总时间复杂度为 O(n log k)。

综上所述，总的时间复杂度为 O(n log k)。

2. 空间复杂度

映射（Map）的空间复杂度：
- 映射中的键的数量等于出发机场的数量，假设最多有 m 个不同的出发机场。
- 每个出发机场对应一个优先队列，每个优先队列的大小最多为 n（因为所有机票都可能从同一个机场出发）。
- 因此，映射的空间复杂度为 O(m + n)。
栈空间（递归调用栈）的空间复杂度：
- DFS 过程中，最坏情况下可能需要 n 层递归调用栈，因此栈空间复杂度为 O(n)。
最终行程列表（itinerary）的空间复杂度：
- 最终行程列表的大小等于机票数量加一（因为每张机票对应一个行程中的机场，且包括起点）。
- 因此，行程列表的空间复杂度为 O(n)。

综上所述，总的空间复杂度为 O(m + 2n)，可以简化为 O(n)，因为 m 通常小于或等于 n。

五、总结知识点

Java Collections Framework:
- HashMap: 用于存储出发机场到目的机场列表的映射。
- PriorityQueue: 优先队列，用于存储每个出发机场的目的机场，并自动按照字典序排序。
Java 泛型:
- 使用泛型 List<List<String>> 和 Map<String, PriorityQueue<String>> 来确保类型安全。
Java 方法重载:
- putIfAbsent 方法是 Map 接口的一个默认方法，它仅在键不存在时才将键值对放入映射中。
递归:
- dfs 方法是一个递归方法，用于深度优先搜索所有可能的行程。
集合操作:
- offer 方法用于将元素添加到优先队列中。
- poll 方法用于从优先队列中移除并返回队列头部的元素。
列表操作:
- add 方法用于将元素添加到列表的末尾。
- reverse 方法用于反转列表中的元素顺序。
字符串操作:
- 字符串比较和排序是基于字典序进行的。
基础控制结构:
- for 循环用于遍历机票列表。
- while 循环用于在 dfs 方法中处理所有可能的目的地。
条件表达式:
- null 检查和 isEmpty 方法用于检查优先队列是否为空。