C/C++教程

leetcode 332

本文主要是介绍leetcode 332,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

问题解析:

1.将机场看作是一个个节点,航班则是一条条边,字典排序看作是边的权值,那么实际上就是求解一条欧拉回路或者欧拉通路,其中越靠前的边的权值应该尽可能小。

思路:

1.假设当前起点YYY已经给出,我们从可以选择的边[YYY,XXX]选择权值最小也就是字典序最小的那条,将XXX加入结果栈res当中,然后从待选边集删除这条边,将当前节点改为XXX,递归调用1。
2.如果当前结果栈res元素个数刚好等于边集的个数+1,那么找到了解。
3.如果当前结果栈res元素个数刚好小于边集的个数+1,但是又无路可走,证明进入了死胡同,需要回溯。
4.如果需要回溯,则需要将当前结果栈的栈顶元素弹出,已经选择的边不再加入待选边集,重复1。

待选边集的实现
对于每一个节点,既需要表示其是否已经选过又需要依据字典排序
所以选择了

unordered_map<string, map<string, int>> ref;

代码:

class Solution {
public:
    vector<string> res;
    int res_size;
    unordered_map<string,map<string,int>> ref;
    bool backtrack(string start)
    {
        if(res_size==res.size())
            return true;
        for(auto &t : ref[start])
        {
            if(t.second>0)
            {
                res.push_back(t.first);
                t.second--;
                if(backtrack(t.first))
                    return true;
                else
                {
                    res.pop_back();
                    t.second++;
                }
            }
        }
        return false;
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        res.clear();
        res_size=tickets.size()+1;
        for(auto t:tickets)
        {
            ref[t[0]][t[1]]++;
        }
        res.push_back("JFK");
        backtrack("JFK");
        return res;
    }
};
这篇关于leetcode 332的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!