给你一份航线列表 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;
}
};
标签:tickets,used,return,res,行程,332,重新安排,vector,path
From: https://www.cnblogs.com/lihaoxiang/p/17321705.html