未分類

Reconstruct Itinerary

DepthFirstSearch, Go, Graph, 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 form at least one valid itinerary.

Example 1:

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

Example 2:

1
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.

提示 解題應用
Graph 相鄰表製作

Default:

1
2
3
func findItinerary(tickets [][]string) []string {
}

解答思路:

題目有提到要依最小詞彙順序的解答為主，因此倒不如在一開始就先將資料做排序，然而資料是一個二元陣列(每份資料由起點與終點的機場縮寫組成)，這邊就只好自行定義一個排序的規則，先比較起點資料間的字串，而如果起點相同再比較終點的字串，排序之後就可以得到一個由小排至大的機票，接下來就可以開始來處理搭乘順序的問題了，不過如果就這樣依序從”JFK”開始遵從先前排序的機票來搭乘(碰到有多個終點時選擇詞彙最小的機票)，還是會碰上如下的情況:

1
2
3
4
[["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]
X: JFK → KUL
O: JFK → NRT → JFK → KUL

也就是中間略過數個班機而沒使用上全部的機票，所以最好的辦法是從終點找回起點，不過可惜的是我們沒有辦法預先知道最終的目地是哪一站，因此從JFK開始如果發現有以該點做為起點的班機(有終點站)，就先將其放入stack之中，接著取出對應的終點(從最小詞彙順序開始取)當作下一個起點，而如果該點作為起點時並沒有終點(也就表示已到達最終的目地)，此時便將該點放入結果陣列(要從結尾開始往前放，因為是從最終目地開始往回找起)並從stack取出下一個起點，不斷重覆上述動作直到stack為空為止就可以找出整個搭乘順序的過程了。

程式碼解說:

因為需要自行定義一個排序的規則來排序機票，一開始便定義Len(),Swap(),Less()三個function，前面兩個function與一般排序規則並無差別，而主要複寫的便是Less()的比較，注意資料是一個二元陣列(每份資料由起點與終點的機場縮寫組成)，先比較起點資料間的字串，而如果起點相同再比較終點的字串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type TicketsSorter [][]string
func (a TicketsSorter) Len() int      { return le
n(a) }
func (a TicketsSorter) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a TicketsSorter) Less(i, j int) bool {
	if a[i][0] < a[j][0] {
		return true
	} else if a[i][0] == a[j][0] {
		if a[i][1] < a[j][1] {
			return true
		}
		return false
	}
	return false
}

再來是定義stack的結構，這邊是以LinkedList來實作包含字串(儲存機場縮寫)與下一個stack節點的位置

1
2
3
4
type StackNode struct {
	Val  string
	Next *StackNode
}

接著就可以來找出整個搭乘順序的過程，先初始化用來儲存結果的陣列與放入第一個節點至stack(從JFK開始)，再將資料的起點與終點整理成相鄰表、關係表之前把機票代入先前自訂的規則來做排序，排序後才一一取出機票的起點與終點整理成相鄰表，這邊是以hashmap來儲存，其中key值為起點而value則是一陣列包含所能抵達的終點(依最小詞彙排序)

1
2
3
4
5
6
7
8
9
var dest string
var tmp *StackNode
result := []string{}
top := &StackNode{"JFK", nil}
sort.Sort(TicketsSorter(tickets))
hashMap := make(map[string][]string)
for _, ticket := range tickets {
	hashMap[ticket[0]] = append(hashMap[ticket[0]], ticket[1])
}

從stack取出起點JFK開始如果發現該班機有終點站，就先將對應的終點(從最小詞彙順序開始取)放入stack之中(記得將對應的終點從相鄰表移除)，而如果該點作為起點時並沒有終點(對應的終點陣列長度為0，表示已到達最終的目地)，此時便將該點放入結果陣列(要從結尾開始往前放，因為是從最終目地開始往回找起)並從stack取出下一個起點，不斷重覆上述動作直到stack為空為止就可以找出整個搭乘順序的過程了

1
2
3
4
5
6
7
8
9
10
11
12
for top != nil {
	dest = top.Val
	if len(hashMap[dest]) == 0 {
		result = append([]string{dest}, result...)
		top = top.Next
	} else {
		tmp = &StackNode{hashMap[dest][0], top}
		top = tmp
		hashMap[dest] = hashMap[dest][1:]
	}
}
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
type TicketsSorter [][]string
func (a TicketsSorter) Len() int      { return len(a) }
func (a TicketsSorter) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a TicketsSorter) Less(i, j int) bool {
	if a[i][0] < a[j][0] {
		return true
	} else if a[i][0] == a[j][0] {
		if a[i][1] < a[j][1] {
			return true
		}
		return false
	}
	return false
}
type StackNode struct {
	Val  string
	Next *StackNode
}
func findItinerary(tickets [][]string) []string {
	var dest string
	var tmp *StackNode
	result := []string{}
	top := &StackNode{"JFK", nil}
	sort.Sort(TicketsSorter(tickets))
	hashMap := make(map[string][]string)
	for _, ticket := range tickets {
		hashMap[ticket[0]] = append(hashMap[ticket[0]], ticket[1])
	}
	for top != nil {
		dest = top.Val
		if len(hashMap[dest]) == 0 {
			result = append([]string{dest}, result...)
			top = top.Next
		} else {
			tmp = &StackNode{hashMap[dest][0], top}
			top = tmp
			hashMap[dest] = hashMap[dest][1:]
		}
	}
	return result
}

總結:

有數張從A往B地的機票，由特定的起點開始要找出整個搭乘順序的過程(使用全部的機票)，如果有多個解答的情況則以最小詞彙順序的解答為主，因此一開始就先將資料做排序(二元陣列:每份資料由起點與終點的機場縮寫組成)，這邊自行定義一個排序的規則，先比較起點資料間的字串，而如果起點相同再比較終點的字串，排序之後就可以得到一個由小排至大的機票，接下來就可以開始來處理搭乘順序的問題，為了避免中間略過數個班機而沒使用上全部的機票，所以最好的辦法是從終點找回起點，不過可惜的是無法預先知道最終的目地是哪一站，因此從特定的起點開始如果發現有以該點做為起點的班機(有終點站)，就先將其放入stack之中，接著取出對應的終點(從最小詞彙順序開始取)當作下一個起點，而如果該點作為起點時並沒有終點(也就表示已到達最終的目地)，此時便將該點放入結果陣列(要從結尾開始往前放，因為是從最終目地開始往回找起)並從stack取出下一個起點，不斷重覆上述動作直到stack為空為止就可以找出整個搭乘順序的過程了。

分享到