代码之家 › 专栏 › 技术社区 › Ganpat

仅当集合为空时弹出值背后的直觉

graph-traversal graph algorithm c++

Ganpat · 技术社区 · 8 年前

我正在解决一个关于Leetcode的问题: https://leetcode.com/problems/reconstruct-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 反向矢量;但我不明白直觉在该if条件之后:

只有当集合为空时才从堆栈弹出,如何确保该测试用例得到处理?

2 回复 | 直到 8 年前

xskxzr 8 年前

问题本质上是找到 Eulerian path 在有向图中,每对[从,到]代表一条边。

向上投票的答案使用一种称为 Hierholzer's algorithm (Hierholzer算法最初用于寻找欧拉周期 ,但很容易修改为欧拉语路径 ). 一般来说

继续跟踪未使用的边缘并移除它们,直到卡住为止。 一旦陷入困境,我们将返回到当前路径中具有未使用边的最近顶点,然后重复该过程,直到所有边都被使用。

强调的部分是您的解决方案与经过投票的解决方案之间的差异。

P、虽然算法很简单,但正确性的证明并不是那么简单。如果你对它感兴趣,你可以在互联网上搜索它。

thebenman 8 年前

访问后 to 城市被移除,这实际上意味着 到 城市作为中介 from 已访问城市,无需考虑下次相应的 从…起 访问城市,否则它将是一个没有停止条件的永无止境的循环。

因此 if 语句是检查是否所有 到 a城市 从…起 这座城市已经参观过了。它就像一个访问阵列,跟踪迄今为止访问的所有城市。