leetcode Reconstruct Itinerary

leetcode Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

  1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
  2. All airports are represented by three capital letters (IATA code).
  3. You may assume all tickets may form at least one valid itinerary.

Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

题目地址: leetcode Reconstruct Itinerary

题意:给定一些飞机票,让你从中找出一个序列可以全部用完。要求如下

  • 从JFK出发。
  • 如果有多个解,输出字典序最小的。

思路:

这题其实很水,只要你这些数据结构掌握的好的话。

  • 返回的答案必为n+1,n为tickets的个数
  • 一张飞机票只能用一次,所以要计数。(可能重复)
  • 字典序最小只需要保证我们遍历的时候从小到大遍历即可。so,建图的时候邻接表边从小到大。
    • 所以C++用map, Python 排序后OrderedDict.

以上所有的情况都考虑到了,然而没有1A我很惭愧。。。因为一时激动把DFS最后的return false 写成true了。。。

再ps: 题目其实可以增加难度的,比如,有的飞机票就是用不到啊[a,b ] [b,c] [f,g]最后一张用不到,让你求最多跑多少,多解输出最小序列。怎么实现就留给读者吧:)

C++

 

Python

 

本题是leetcode 332  Reconstruct Itinerary 题解,

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Reconstruct Itinerary
本文地址:https://www.hrwhisper.me/leetcode-reconstruct-itinerary/

打赏一杯咖啡钱呗

Leetcode , , . permalink.

9 thoughts on “leetcode Reconstruct Itinerary

Leave a Reply

Your email address will not be published. Required fields are marked *