每日Hard - Day 9

Tags

日期	2022年10月7日
是否独立完成	是
涉及算法	深度优先搜索、欧拉回路

---

题面

LeetCode 332. 重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

• 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

示例 1：

输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

示例 2:

输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。

---

题解

显然这道题最基本的结构是图。因为要查找字典序最小的行程组合，我们只需要排序后贪心地进行深度优先搜索就行了。

class Solution {
private:
    vector<string> res;
    unordered_map<string, vector<string>> map;
    bool found = false;
    int cnt = 0;
    void dfs(string cur) {
        if (found) return;
        res.push_back(cur);
        if (cnt == 0) {
            found = true;
            return;
        }

        for (int i = map[cur].size() - 1; i >= 0; i--) {
            if (map[cur][i] == "") continue;
            string next = map[cur][i];
            map[cur][i] = "";
            cnt--;
            dfs(next);
            if (found) return;
            cnt++;
            res.pop_back();
            map[cur][i] = next;
        }

    }
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for (vector<string> s : tickets) {
            map[s[0]].push_back(s[1]);
            cnt++;
        }
        for (auto& i : map) {
            sort(i.second.begin(), i.second.end());
            reverse(i.second.begin(), i.second.end());
        }
        dfs("JFK");
        return res;

    }
};

但是我的办法是删删改改后的蠢办法，只能勉强通过。用上优先队列可以更优雅地实现快速找到字典序最小的下一个节点。还需要用上欧拉回路的一个性质，就是入度和出度相差为1的节点必定是最后一个节点。用上这个性质就可以写出更简洁的代码了。

---

有的没的

国庆总结

今年度过了一个充实的国庆假期。

30号在玉泉上了课之后去了青芝坞的花先生厨房吃午饭。店里的环境很棒，牛河炒的中规中矩，炒豆角里的炸蛋碎碎简直是神来之笔，咸蛋黄炸蘑菇的咸蛋黄存在感很强，红烧肉吃的满嘴流油超级满足。

1号和2号在寝室连扣了两天代码，写了计网的TCP套接字编程的作业。项目在https://github.com/Cyclohexatriene/Lab7 ，昨天加了最后一块碎片正式完工，但是实验报告还没来得及写。非常有成就感！

3号写了信息检索的爬虫作业，IP被豆瓣封了若干次，最后换了手机两张卡的热点才爬完全部结果。第一次自己写爬虫代码，觉得还是学到不少东西的。

4号和胖喜鹊同学去了灵隐寺玩，下山后沿着西湖从北山街逛到了湖滨银泰，被西湖的风吹得有点迷糊。淋了点小雨，走得很累，但是玩得很开心！

5号和6号写了暑假小学期的报告，个人报告糊弄了不到1500字交上去了，写得非常求是了可以说是。还玩了《守望先锋》（归来），雾子太好看了，新老婆。后来发现日语声优还和徐伦是同一个人，双厨狂喜。

7号本来打算参加一下LeetCode的秋季赛，但是好多同学来问了爬虫的问题，不得不说，爬虫真是太玄学了。竞赛后来做了一道题就摆了，有好多必须回的消息，干扰太大了，没法专心思考。而且咕了太久的刷题了，脑子有点转不动（所以今天也摇了一道水Hard做做，嘿嘿）。

刚才发现博客里好多图片显示不出来。或者说，只有首页的图片能显示。目测是相对路径的问题，回头再研究下。修好了捏。