LeetCode332 重新安排行程

发表于 | 分类于 |
字数统计: 512 | 阅读时长 ≈ 2

链接： https://leetcode-cn.com/problems/reconstruct-itinerary/

题面

给定一个人坐过的一些飞机的起止机场，已知这个人从 JFK 起飞，那么这个人是按什么顺序飞的；如果存在多种可能性，返回字母序最小的那种。要求所有的机票必须都用一次且只能用一次。

解法

这个题目的做法就肯定是DFS了，但是题目要求找到字母序最小的结果
所以可以用到一个set来存储所有的下个结点，但是由于题目中存在多张相同的机票
所以需要使用到multiset
递归的时候也和常规题目有所区别，由于是用到了set，所以没法直接erase
erase会改变迭代器的位置导致迭代器找不到之前的位置
解法巧妙的运用了栈或者说是深搜的特点，如果没有下个结点了，就将当前结点入栈
这一定是当目前为止的终点 需要仔细体会
也是一种新的思路 需要掌握
代码提供两种解法，其实是一样的思路，只是一个使用递归函数实现，另一个使用栈实现。

代码

解法一 DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    map<string, multiset<string>> graph;
    vector<string> ans;
    int n, flag;
    void dfs(string place) {
        while(!graph[place].empty()) {
            string s = * graph[place].begin();
            graph[place].erase(graph[place].begin());
            dfs(s);
        }
        ans.push_back(place);
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        n = tickets.size();
        for (auto item: tickets) {
            graph[item[0]].insert(item[1]);
        }
        dfs("JFK");
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

解法一 用栈实现

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
class Solution {
public:
    map<string, multiset<string>> graph;
    vector<string> ans;
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for (auto item: tickets) {
            graph[item[0]].insert(item[1]);
        }
        vector<string> s;
        s.push_back("JFK");
        while(s.size()) {
            string now = s.back();
            if (graph[now].empty()) {
                ans.push_back(now);
                s.pop_back();
            }
            else {
                s.push_back(*graph[now].begin());
                graph[now].erase(graph[now].begin());
            }
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};