珠海开发网站公司,网站建设公司南宁,建网站网站,金华建设局网站力扣题目链接
给定一个机票的字符串二维数组 [from, to]#xff0c;子数组中的两个成员分别表示飞机出发和降落的机场地点#xff0c;对该行程进行重新规划排序。所有这些机票都属于一个从 JFK#xff08;肯尼迪国际机场#xff09;出发的先生#xff0c;所以该行程必须从…力扣题目链接
给定一个机票的字符串二维数组 [from, to]子数组中的两个成员分别表示飞机出发和降落的机场地点对该行程进行重新规划排序。所有这些机票都属于一个从 JFK肯尼迪国际机场出发的先生所以该行程必须从 JFK 开始。
提示
如果存在多种有效的行程请你按字符自然排序返回最小的行程组合。例如行程 [JFK, LGA] 与 [JFK, LGB] 相比就更小排序更靠前所有的机场都用三个大写字母表示机场代码。假定所有机票至少存在一种合理的行程。所有的机票必须都用一次 且 只能用一次。
解题思路 图的建模把航班信息建模为图其中城市为节点航班为边。构建邻接表来表示图。 排序对目的地进行字母排序确保在深度优先搜索中总是优先访问字母顺序靠前的目的地。 DFS遍历使用深度优先搜索遍历图从起始城市出发一直走到所有可能的目的地记录经过的城市。 路径重建由于深度优先搜索会使得路径顺序反向需要在结果列表中反转顺序以获得正确的行程。
这个方法有效地使用了排序和深度优先搜索来解决旅行路径问题保证了按照字母顺序访问目的地并生成正确的行程路径。
完整代码如下
class Solution:def findItinerary(self, tickets: List[List[str]]) - List[str]:self.adj {}# sort by the destination alphabetically# 根据航班每一站的重点字母顺序排序tickets.sort(keylambda x:x[1])# get all possible connection for each destination# 罗列每一站的下一个可选项for u,v in tickets:if u in self.adj: self.adj[u].append(v)else: self.adj[u] [v]# 从JFK出发self.result []self.dfs(JFK) # start with JFKreturn self.result[::-1] # reverse to get the resultdef dfs(self, s):# if depart city has flight and the flight can go to another citywhile s in self.adj and len(self.adj[s]) 0:# 找到s能到哪里选能到的第一个机场v self.adj[s][0] # we go to the 1 choice of the city# 在之后的可选项机场中去掉这个机场self.adj[s].pop(0) # get rid of this choice since we used it# 从当前的新出发点开始self.dfs(v) # we start from the new airportself.result.append(s) # after append, it will back track to last node, thus the result list is in reversed orderself.adj {}self.adj 用于存储每个城市的邻接表。邻接表是一个字典键是出发城市值是一个列表表示从该城市出发可以到达的目的城市。
tickets.sort(keylambda x: x[1])对 tickets 列表按照每个航班的目的地x[1]进行排序。这样做是为了在后续的处理过程中能优先选择字母顺序靠前的目的地。
for u, v in tickets:if u in self.adj:self.adj[u].append(v)else:self.adj[u] [v]遍历排序后的航班列表为每个出发城市 u 创建一个目的地列表。若 u 已经在 self.adj 字典中则将 v 加入到对应的列表中否则创建一个新的列表。
self.result []
self.dfs(JFK)初始化 self.result 列表用于存储最终的行程路径。调用 dfs 方法从起始城市 JFK 开始进行深度优先搜索。
def dfs(self, s):while s in self.adj and len(self.adj[s]) 0:v self.adj[s][0]self.adj[s].pop(0)self.dfs(v)self.result.append(s)在 dfs 方法中首先检查当前城市 s 是否有可用的航班即 s 是否在 self.adj 中且有目的地。如果有取出列表中的第一个目的地 v因为航班列表已按字母排序过选择第一个保证了字母顺序并从列表中删除这个目的地。然后递归调用 dfs 方法继续从 v 出发。递归完成后将当前城市 s 添加到 self.result 中。注意self.result 中的城市顺序是逆序的因为每次递归都会先处理后续的城市最后返回到当前城市。
return self.result[::-1]最后返回 self.result 的反转列表即按照正确的旅行顺序输出最终的行程路径。
