給定一個(gè)機(jī)票的字符串二維數(shù)組 [from, to]，子數(shù)組中的兩個(gè)成員分別表示飛機(jī)出發(fā)和降落的機(jī)場(chǎng)地點(diǎn)，對(duì)該行程進(jìn)行重新規(guī)劃排序。所有這些機(jī)票都屬于一個(gè)從 JFK（肯尼迪國際機(jī)場(chǎng)）出發(fā)的先生，所以該行程必須從 JFK 開始。

說明:

如果存在多種有效的行程，你可以按字符自然排序返回最小的行程組合。例如，行程 [“JFK”, “LGA”] 與 [“JFK”, “LGB”] 相比就更小，排序更靠前
所有的機(jī)場(chǎng)都用三個(gè)大寫字母表示（機(jī)場(chǎng)代碼）。
假定所有機(jī)票至少存在一種合理的行程。
示例 1:

輸入: [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]]
輸出: [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”]

代碼

class Solution {List<String> res=new ArrayList<>();public List<String> findItinerary(List<List<String>> tickets) {Map<String,PriorityQueue<String>> map=new HashMap<>();for(List<String> list:tickets)//創(chuàng)建鄰接表{if(!map.containsKey(list.get(0)))map.put(list.get(0),new PriorityQueue<>());map.get(list.get(0)).add(list.get(1));}getItinerary(map,"JFK");Collections.reverse(res);//逆轉(zhuǎn)return res;}public void getItinerary( Map<String,PriorityQueue<String>> map,String cur) {while (map.containsKey(cur)&&!map.get(cur).isEmpty())//對(duì)連接的節(jié)點(diǎn)dfs，并且刪除連接的邊getItinerary(map,map.get(cur).poll()); res.add(cur);} }

總結(jié)

以上是生活随笔為你收集整理的leetcode332. 重新安排行程（dfs）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。