我正在求解leetcode上的问题:https://leetcode.com/problems/reconscond--itinerary/description/。问题是:
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.
对于例如,如果tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
,输出应为: ["JFK", "MUC", "LHR", "SFO", "SJC"]
。
我编写了以下代码,该代码(可以理解(在输入[["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]
上断开,因为根据我的代码,节点" nrt"仍未访问:
class Solution {
public:
vector<string> findItinerary(vector<pair<string, string>> tickets) {
if(tickets.empty()) return vector<string>();
vector<string> result;
unordered_map<string, multiset<string>> itinerary;
for(auto& each : tickets)
itinerary[each.first].insert(each.second);
stack<string> myStack;
myStack.push("JFK");
while(!myStack.empty()) {
string topVal=myStack.top();
result.push_back(topVal);
myStack.pop();
if(!itinerary[topVal].empty()) {
myStack.push(*itinerary[topVal].begin());
itinerary[topVal].erase(itinerary[topVal].begin());
}
}
return result;
}
};
为了克服这一点,其中一种被投资的解决方案提出了这一小变化:
class Solution {
public:
vector<string> findItinerary(vector<pair<string, string>> tickets) {
if(tickets.empty()) return vector<string>();
vector<string> result;
unordered_map<string, multiset<string>> itinerary;
for(auto& each : tickets)
itinerary[each.first].insert(each.second);
stack<string> myStack;
myStack.push("JFK");
while(!myStack.empty()) {
string topVal=myStack.top();
if(itinerary[topVal].empty()) { //--->this if condition
result.push_back(topVal);
myStack.pop();
}
else {
myStack.push(*itinerary[topVal].begin());
itinerary[topVal].erase(itinerary[topVal].begin());
}
}
reverse(result.begin(), result.end());
return result;
}
};
现在,我使用示例[["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]
处理了此代码,并看到了如何以反向方式将值插入result
向量;但是如果条件:
仅在集合为空时才从堆栈中弹出,请确保处理此测试案例?
问题本质上是在有向图中找到一个欧拉(Eulerian(路径,其中每一个(从,到(对一个边缘代表一个边缘。
upiteded答案使用一种称为Hierholzer算法的算法(Hierholzer的算法最初用于查找Eulerian cycle ,但是对于Eulerian PATH (进行了修改很容易。通常,它
继续遵循未使用的边缘并将其删除,直到我们卡住为止。一旦我们卡住了,我们就会回到未使用边缘的当前路径中最近的顶点,我们重复该过程直到使用了所有边缘。
强调的一部分是您的解决方案和投票解决方案之间的区别。
P.S。尽管该算法很简单,但正确性的证明并不是那么微不足道。如果您对此感兴趣,则可以在Internet上进行搜索。
访问to
城市后,它将被删除,这实际上意味着to
City作为中级from
City已访问过,不需要在下一次访问相应的from
城市时被视为将是一个永无止境的循环,没有停止条件。
因此,if
语句是检查from
城市的所有to
城市是否已经访问的情况。这几乎就像一个访问的阵列,跟踪到目前为止所参观的所有城市。