526互联

332. 重新安排行程

发布时间 2023-04-15 19:34:35作者: xiazichengxi

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

> 我的解法
用常规的回溯，当测试用例一多，就不能通过，所以标准解法用map的关键字有序性来进行回溯。

class cmp{
public:
    bool operator()(const vector<string> &lhs,const vector<string> &rhs){
        for (int i = 0; i < lhs.size(); i++) {
            if (lhs[i] == rhs[i]) continue;
            else return lhs[i] < rhs[i];
        }
        return false;
    }
};

class Solution {
private:
    bool use_tickets(vector<bool> &used) {
        for (const auto& p : used) {
            if (p == false) return false;
        }
        return true;
    }
    void traversal(vector<vector<string>>& tickets, vector<bool> &used) {
        if (use_tickets(used)) {
            res.emplace_back(path);
            return;
        }
        for (int i = 0; i < tickets.size(); i++) {
            if(used[i]) continue;
            else if (path.empty() && tickets[i][0] == "JFK" && used[i] == false) {
                path.emplace_back(tickets[i][0]);
                path.emplace_back(tickets[i][1]);
                used[i] = true;
                traversal(tickets, used);
                used[i] = false;
                path.pop_back();
                path.pop_back();
            }
            else if (!path.empty() && path.back() == tickets[i][0] && used[i] == false) {
                path.emplace_back(tickets[i][1]);
                used[i] = true;
                traversal(tickets, used);
                used[i] = false;
                path.pop_back();
            }
            else continue;
        }
    }
    vector<string> tickets_sort(vector<vector<string>>& res) {
        if (res.empty()) return { "" };
        std::priority_queue<vector<string>,vector<vector<string>>,cmp> que;
        for(const auto &ele:res){
            if(que.empty())
            {
                que.push(ele);
            }
            else{
                que.push(ele);
                que.pop();
            }
        }
        return que.top();
        // std::sort(res.begin(), res.end(),
        //     [](const vector<string>& lhs, const vector<string>& rhs)->bool {
        //         for (int i = 0; i < lhs.size(); i++) {
        //             if (lhs[i] == rhs[i]) continue;
        //             else return lhs[i] < rhs[i];
        //         }
        //         return false;
        //     });
        // return res[0];
    }
public:
    vector<vector<string>> res;
    vector<string> path;
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        if (tickets.size() == 1) return tickets[0];
        res.clear();
        path.clear();
        vector<bool> used(tickets.size(),false);
        traversal(tickets, used);
        return tickets_sort(res);
    }
};

> 标准解法

class Solution {
private:
    bool traversal(string ticket,int ticknum){
        if(res.size() == ticknum + 1) return true;
        bool find = false;
        for(auto &ele: mp[ticket]){
            if(ele.second > 0){
                string arrive = ele.first;
                res.emplace_back(arrive);
                ele.second--;
                find = traversal(arrive,ticknum);
                if(find) return true;
                ele.second++;
                res.pop_back();
            }
        }
        return false;
    }
public:
    map<string,map<string,int>> mp;
    vector<string> res;
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        if (tickets.size() == 1) return tickets[0];
        mp.clear();
        res.clear();
        for(const auto &element:tickets){
            mp[element[0]][element[1]]++;
        }
        res.emplace_back("JFK");
        traversal("JFK",tickets.size());
        return res;
    }
};