• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode332.重新安排行程|ReconstructItinerary

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/10261960.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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 form at least one valid itinerary.

Example 1:

Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

Example 2:

Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"].
             But it is larger in lexical order.

给定一个机票的字符串二维数组 [from, to],子数组中的两个成员分别表示飞机出发和降落的机场地点,对该行程进行重新规划排序。所有这些机票都属于一个从JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 出发。

说明:

  1. 如果存在多种有效的行程,你可以按字符自然排序返回最小的行程组合。例如,行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小,排序更靠前
  2. 所有的机场都用三个大写字母表示(机场代码)。
  3. 假定所有机票至少存在一种合理的行程。

示例 1:

输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]

示例 2:

输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]
解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。

144ms
 1 class Solution {
 2     var graph: [String: [String]] = [:]
 3     var route: [String] = []
 4     func findItinerary(_ tickets: [[String]]) -> [String] {
 5         
 6         for t in tickets {
 7             var city = graph[t[0]] ?? []
 8             city.append(t[1])
 9             graph[t[0]] = city
10         }
11         
12         for key in graph.keys {
13             graph[key]?.sort()
14         }
15         self.visit("JFK")
16         return self.route
17     }
18     
19     private func visit(_ city: String) {
20         if let dests = graph[city] {
21             while !graph[city]!.isEmpty {
22                 let dest = graph[city]!.removeFirst()
23                 self.visit(dest)
24             }
25         }
26         self.route.insert(city, at: 0)
27     }
28 }

568ms

  1 class Solution {
  2      func findItinerary(_ tickets: [[String]]) -> [String] {
  3         
  4         let graph = buildGraph(tickets)
  5         var res = [String]()
  6         dfs(graph, from: "JFK",0, &res)
  7         
  8         return res
  9     }
 10 
 11     @discardableResult func dfs(_ graph : Graph<String>, from : String ,_ visitedCount : Int, _ res : inout [String]) -> Bool {
 12         res.append(from)
 13         if visitedCount == graph.edges.count {
 14             return true
 15         }
 16         let edges = graph.edgesFrom(graph.createVertex(from)).sorted{$0.to.data < $1.to.data}
 17         for edge in edges where edge.visited == false {
 18             edge.visited = true
 19             if dfs(graph, from: edge.to.data, visitedCount+1, &res) == true {
 20                 return true
 21             }
 22             edge.visited = false
 23         }
 24         res.removeLast()
 25         return false
 26         
 27     }
 28     
 29     func buildGraph(_ tickets : [[String]]) -> Graph<String> {
 30         let graph = Graph<String>()
 31         for i in 0..<tickets.count {
 32             let ticket = tickets[i]
 33             let from = graph.createVertex(ticket[0])
 34             let to = graph.createVertex(ticket[1])
 35             graph.addDirectedEdge(from, to: to, withWeight: Double(i))
 36         }
 37         return graph
 38     }
 39     //===================实现Graph的分割线======================
 40     struct Vertex<T> : Equatable,Hashable where T : Hashable {
 41         var data : T
 42         var index : Int
 43         
 44         public var description: String {
 45             return "\(index):\(data)"
 46         }
 47     }
 48 
 49     public class Edge<T>: Equatable,Hashable where T: Hashable {
 50         public static func == (lhs: Solution.Edge<T>, rhs: Solution.Edge<T>) -> Bool {
 51             return lhs.from == rhs.from && lhs.to == rhs.to && lhs.weight == rhs.weight
 52         }
 53         
 54         public let from: Vertex<T>
 55         public let to: Vertex<T>
 56         
 57         public let weight:Double?
 58         
 59         public var visited : Bool
 60         
 61         public var hashValue:Int {
 62             var string = "\(from.description)\(to.description)"
 63             if weight != nil{
 64                 string.append("\(weight!)")
 65             }
 66             return string.hashValue
 67         }
 68         
 69         init(from: Vertex<T>, to: Vertex<T>, weight: Double?, visited: Bool) {
 70             self.from = from
 71             self.to = to
 72             self.weight = weight
 73             self.visited = visited
 74         }
 75     }
 76     
 77 
 78     
 79     private class EdgeList<T> where T: Hashable {
 80         
 81         var vertex: Vertex<T>
 82         var edges: [Edge<T>]?
 83         
 84         init(vertex: Vertex<T>) {
 85             self.vertex = vertex
 86         }
 87         
 88         func addEdge(_ edge: Edge<T>) {
 89             edges?.append(edge)
 90         }
 91         
 92     }
 93     
 94     
 95     class Graph<T> where T : Hashable {
 96         var vertices : [Vertex<T>] {
 97             var vertices = [Vertex<T>]()
 98             for edgeList in adjacencyList {
 99                 vertices.append(edgeList.vertex)
100             }
101             return vertices
102         }
103         
104         private var adjacencyList: [EdgeList<T>] = []
105         
106         open var edges: [Edge<T>] = [Edge<T>]()
107 
108         open func addDirectedEdge(_ from: Vertex<T>, to: Vertex<T>, withWeight weight: Double?) {
109             // works
110             let edge = Edge(from: from, to: to, weight: weight, visited: false)
111             let edgeList = adjacencyList[from.index]
112             if edgeList.edges != nil {
113                 edgeList.addEdge(edge)
114             } else {
115                 edgeList.edges = [edge]
116             }
117             edges.append(edge)
118         }
119         
120         open func createVertex(_ data: T) -> Vertex<T> {
121            
122             let matchingVertices = vertices.filter { vertex in
123                 return vertex.data == data
124             }
125             
126             if matchingVertices.count > 0 {
127                 return matchingVertices.last!
128             }
129 
130             let vertex = Vertex(data: data, index: adjacencyList.count)
131             adjacencyList.append(EdgeList(vertex: vertex))
132             return vertex
133         }
134         
135         open func edgesFrom(_ sourceVertex: Vertex<T>) -> [Edge<T>] {
136             return adjacencyList[sourceVertex.index].edges ?? []
137         }
138                 
139     }
140 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
swift REPL发布时间:2022-07-14
下一篇:
swift - 不同target 之间 的跳转发布时间:2022-07-14
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap