题目
给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
- 例如，行程
["JFK", "LGA"]与["JFK", "LGB"]相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
思路
另一种概念的排列
class Solution {
public:
vector<string> path;
vector<int> path_index;
bool search_first_ticket(vector<vector<string>>& tickets, vector<bool>& used_tickets)
{
int index = -1;
for(int i = 0; i < tickets.size(); ++i)
{
if(path.empty())
{
if(used_tickets[i] == false && tickets[i][0] == "JFK")
{
if(index == -1) index = i;
else
{
if(tickets[i][1] < tickets[index][1]) index = i;
}
}
}
else
{
if(used_tickets[i] == false && tickets[i][0] == path[path.size() - 1])
{
if(index == -1) index = i;
else
{
if(tickets[i][1] < tickets[index][1]) index = i;
}
}
}
}
if(index == -1) return false;
if(path.empty()) path.emplace_back(tickets[index][0]);
path.emplace_back(tickets[index][1]);
path_index.emplace_back(index);
used_tickets[index] = true;
return true;
}
void findItineraryAux(vector<vector<string>>& tickets)
{
vector<bool> used_tickets(tickets.size(), false);
for(int i = 0; i < path_index.size(); ++i) used_tickets[path_index[i]] = true;
for(int i = 0; i < tickets.size(); ++i)
{
if(!search_first_ticket(tickets, used_tickets)) return;
findItineraryAux(tickets);
if(path.size() == tickets.size() + 1) return;
path.pop_back();
if(path.size() == 1) path.pop_back();
path_index.pop_back();
}
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
findItineraryAux(tickets);
return path;
}
};
写了一个半小时
又调了一个小时，第80个案例超时
class Solution {
public:
vector<string> path;
vector<int> path_index;
void findItineraryAux(vector<vector<string>>& tickets)
{
vector<bool> used_tickets(tickets.size(), false);
for(int i = 0; i < path_index.size(); ++i) used_tickets[path_index[i]] = true;
int index = -1;
for(int i = 0; i < tickets.size(); ++i)
{
if(path.empty())
{
if(used_tickets[i] == false && tickets[i][0] == "JFK")
{
if(index == -1) index = i;
else
{
if(tickets[i][1] < tickets[index][1]) index = i;
}
}
}
else
{
if(used_tickets[i] == false && tickets[i][0] == path[path.size() - 1])
{
if(index == -1) index = i;
else
{
if(tickets[i][1] < tickets[index][1]) index = i;
}
}
}
if(i < tickets.size() - 1) continue;
if(index == -1) return;
if(path.empty()) path.emplace_back(tickets[index][0]);
path.emplace_back(tickets[index][1]);
path_index.emplace_back(index);
used_tickets[index] = true;
findItineraryAux(tickets);
if(path.size() == tickets.size() + 1) return;
path.pop_back();
if(path.size() == 1) path.pop_back();
path_index.pop_back();
index = -1;
i = -1;
}
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
findItineraryAux(tickets);
return path;
}
};
又调了半个小时，第80个案例依然超时
class Solution {
public:
vector<string> path;
vector<int> path_index;
void findItineraryAux(vector<vector<string>>& tickets)
{
string next_ticket;
if(path.empty()) next_ticket = "JFK";
else next_ticket = path[path.size() - 1];
int i = 0;
for(; i < tickets.size(); ++i)
{
if(tickets[i][0] == next_ticket) break;
}
if(i == tickets.size()) return;
for(; i < tickets.size() && tickets[i][0] == next_ticket; ++i)
{
if(find(path_index.begin(), path_index.end(), i) != path_index.end()) continue;
if(path.empty()) path.emplace_back(tickets[i][0]);
path.emplace_back(tickets[i][1]);
path_index.emplace_back(i);
if(path.size() == tickets.size() + 1) return;
findItineraryAux(tickets);
if(path.size() == tickets.size() + 1) return;
path.pop_back();
if(path.size() == 1) path.pop_back();
path_index.pop_back();
}
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
sort(tickets.begin(), tickets.end(), [] (const vector<string>& str, const vector<string>& str2){
return str[0] < str2[0] || (str[0] == str2[0] && str[1] < str2[1]);
});
findItineraryAux(tickets);
return path;
}
};
我又写了两个小时，在第80个案例依然超时
class Solution {
public:
vector<string> path;
void findItineraryAux(vector<vector<string>>& tickets, vector<bool>& used_tickets)
{
string next_ticket;
if(path.empty()) next_ticket = "JFK";
else next_ticket = path[path.size() - 1];
int i = 0;
for(; i < tickets.size(); ++i)
{
if(tickets[i][0] == next_ticket) break;
}
if(i == tickets.size()) return;
for(; i < tickets.size() && tickets[i][0] == next_ticket; ++i)
{
if(used_tickets[i]) continue;
if(path.empty()) path.emplace_back(tickets[i][0]);
path.emplace_back(tickets[i][1]);
used_tickets[i] = true;
if(path.size() == tickets.size() + 1) return;
findItineraryAux(tickets, used_tickets);
if(path.size() == tickets.size() + 1) return;
path.pop_back();
if(path.size() == 1) path.pop_back();
used_tickets[i] = false;
}
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
sort(tickets.begin(), tickets.end(), [] (const vector<string>& str, const vector<string>& str2){
return str[0] < str2[0] || (str[0] == str2[0] && str[1] < str2[1]);
});
vector<bool> used_tickets(tickets.size(), false);
findItineraryAux(tickets, used_tickets);
return path;
}
};
又写了十分钟，超时