leetcode 332. Reconstruct Itinerary 重建行程+深度优先遍历DFS+回溯

深碍√TFBOYSˉ_ 2022-06-07 01:12 139阅读 0赞

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:  
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”\].  
All airports are represented by three capital letters (IATA code).  
You may assume all tickets 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.

这道题要求找到最小的字典序的序列，是一个典型的DFS深度优先遍历的应用，不  
过要注意的是这里的使用了优先队列来实现字典序的比较，注意这里是倒序收集节点信息的！！！

代码如下：

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    import java.util.PriorityQueue;
    
    /*
     * 一个简单的DFS写的还是有有问题，需要急需刷第二遍leetcode
     * */
    public class Solution
    {
        
        Map<String, PriorityQueue<String>>  map= new HashMap<>();
        List<String> res = new ArrayList<>();
    
        public List<String> findItinerary(String[][] tickets) 
        {
            if(tickets==null || tickets.length<=0)
                return res;
            for(int i=0;i<tickets.length;i++)
            {
                if(map.containsKey(tickets[i][0])==false)
                {
                    PriorityQueue<String> one=new PriorityQueue<>();
                    map.put(tickets[i][0], one);
                }
                map.get(tickets[i][0]).add(tickets[i][1]);
            }
            dfs("JFK");            
            Collections.reverse(res);
            return res;
        }
    
        public void dfs(String key) 
        {
            if(map.containsKey(key)==false)
            {
                res.add(key);
                return ;
            }else 
            {
                PriorityQueue<String> one=map.get(key);
                while(one.isEmpty()==false)
                    dfs(one.poll());
                res.add(key);
            }
        }
    
         public static void main(String[] args)
         {
            Solution solution=new Solution();
            String[][] tickets={
       {
       "JFK","KUL"},{
       "JFK","NRT"},{
       "NRT","JFK"}};
            solution.findItinerary(tickets);
         }
    }

下面C++的做法

而本题是关于有向图的边的遍历。每张机票都是有向图的一条边，我们需要找出一条经过所有边的路径，那么DFS不是我们的不二选择。先来看递归的结果，我们首先把图建立起来，通过邻接链表来建立。由于题目要求解法按字母顺序小的，那么我们考虑用multiset，可以自动排序。等我们图建立好了以后，从节点JFK开始遍历，只要当前节点映射的multiset里有节点，我们取出这个节点，将其在multiset里删掉，然后继续递归遍历这个节点，由于题目中限定了一定会有解，那么等图中所有的multiset中都没有节点的时候，我们把当前节点存入结果中，然后再一层层回溯回去，将当前节点都存入结果，那么最后我们结果中存的顺序和我们需要的相反的，我们最后再翻转一下即可，

**这道题就这么做吧**

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        vector<string> res;
        vector<string> findItinerary(vector<pair<string, string>> tickets) 
        {
            map<string, multiset<string>> mat;
            for (auto i : tickets)
                mat[i.first].insert(i.second);
    
            dfs(mat, "JFK");
    
            reverse(res.begin(), res.end());
            return res;
        }
    
        void dfs(map<string, multiset<string>>& mat, string key)
        {
            if (mat[key].size() == 0)
                res.push_back(key);
            else
            {
                while (mat[key].empty() == false)
                {
                    string next = *(mat[key].begin());
                    mat[key].erase(mat[key].begin());
                    dfs(mat, next);
                }
                res.push_back(key);
            }
        }
    };