【深度优先搜索】【图论】【推荐】332. 重新安排行程

2024-02-29 16:36

本文主要是介绍【深度优先搜索】【图论】【推荐】332. 重新安排行程,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

作者推荐

动态规划的时间复杂度优化

本文涉及知识点

深度优先搜索 图论

LeetCode332. 重新安排行程

给你一份航线列表 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”] ,但是它字典排序更大更靠后。

提示:
1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi 和 toi 由大写英文字母组成
fromi != toi

基础知识

定义

如果图G中的一个路径包括每个边恰好一次,则该路径称为欧拉路径(Euler path)。
如果一个回路是欧拉路径,则称为欧拉回路(Euler circuit)。

性质

性质一:一个有向图是欧拉回路 ⟺ \iff 所有顶点的入度等于出度且该图是连通图。
性质二:一个有向图是欧拉路径 ⟺ \iff 起点出度等于入度+1,终点入度=出度+1,其它顶点的入度等于出度且该图是连通图。
欧拉路径和回路符合性质比较简单,不证明。下面只证明性质一必定是欧拉回路,性质二是欧拉路径。

证明一

设有向图G符合性质一。
操作一:以任意定点为起点s,选取s的任意临接点n1,删除sn1后,除s外,其它顶点都是出度等于入度,就是进入后,一定会离开。由于顶点的出度和入度是有限的,所以一定会结束,而结束点一定是s(因为只有它入度大于出度)。设删除经过的路径为P1。
最后一次经过s后,可能有些点入度并不为0。
→ { ∗ ∗ 操作二 ∗ ∗ 图 G 删除 P 1 各边,此时余下的边 P 2 仍然符合性质一。 P 1 经过的各点,一定有点 n 2 出度不为 0 。否则与连通图矛盾。 \rightarrow\begin{cases}**操作二**图G删除P1各边,此时余下的边P2仍然符合性质一。\\ P1经过的各点,一定有点n2出度不为0。否则与连通图矛盾。\\ \end{cases} {操作二G删除P1各边,此时余下的边P2仍然符合性质一。P1经过的各点,一定有点n2出度不为0。否则与连通图矛盾。
操作二时:如果有重边,经过几次则删除几条。
以n2为起点对P2进行操作一,得到P3,必定以n2开始和结尾。
用P3替换P1的n2节点。如此往复直到所有节点出度入度为0。

证明二

设有向图G符合性质二,s出度=入度+1,e入度=出度+1。一定存在以s为起点,e为终点的路径P1。选取方法类似证明一,多个出边任选一条出边。图G删除P1后,为P2;P2要么为空,要么符合性质二。

深度优先搜索

题目确保某条从JFK为起点的路径是欧拉路径。
如果是欧拉环路:所有点出度等于入度。
如果不是环路:起点出度-1==入度 终点入度=出度+1,其它节点入度等于出度。
必须确保起点最后访问终点那一支,其它访问顺序按字典需。

DFS 函数

在这里插入图片描述

主函数

DFS(“JFK”)
颠倒m_vRes的顺序
返回m_vRet。

示例和时序图

在这里插入图片描述
在这里插入图片描述

按时间线访问m_vRes的顺序:DAFEACBA。转置(颠倒顺序)后为:ABCAEFAD。

证明:

假定图G的欧拉路径最后一个出度大于1的节点为c,它共有m+1+n条出边,按邻接字典序排序后,第m+1条出边指向终点e。
步骤一:只讨论节点c及之后的路径。设c的临接点按字典序分别为:n[1] …n[m+n+1]。
除DFS(n[1+m] → \rightarrow e)可以直接结束,其它节点都必须等所有A的出边都访问结束(包括n[1+m]),所以 n[1+m] → \rightarrow e 的逆序最先加到vRet。
c → \rightarrow n[n+m+1]是c最后一条出边,故将 n[i+m+1] → \rightarrow c 的逆序放到vRet 中。
c → \rightarrow n[n+m ]是c最倒数第二条出边,故将 n[i+m] → \rightarrow c 的逆序放到vRet 中。
⋯ \cdots 将 n[1+m+1] → \rightarrow c 的逆序放到vRet 中。
⋮ \vdots
⋯ \cdots 将 n[m] → \rightarrow c 的逆序放到vRet 中。
⋯ \cdots n[1 ] → \rightarrow c 的逆序放到vRet 中。
将c 放到vRet 中。
步骤二:将图G 节点c及之后节点的出边都删除。c变成新的终点。
不断持续步骤一二到所有节点的出度为1。注意:c等于e也符合。

代码

核心代码

class Solution {
public:vector<string> findItinerary(vector<vector<string>>& tickets) {std::unordered_map<string, multiset<string>> mNeiBo;for (const auto& v : tickets){mNeiBo[v[0]].emplace(v[1]);}DFS(mNeiBo, "JFK");std::reverse(m_vRet.begin(), m_vRet.end());return m_vRet;}void DFS(std::unordered_map<string, multiset<string>>& mNeiBo,const string& cur){while (mNeiBo[cur].size()){auto next = *mNeiBo[cur].begin();mNeiBo[cur].erase(mNeiBo[cur].begin());DFS(mNeiBo, next);}m_vRet.emplace_back(cur);}vector<string> m_vRet;
};

测试用例

template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}}int main()
{vector<vector<string>> tickets;{Solution sln;tickets = { {"MUC","LHR"},{"JFK","MUC"},{"SFO","SJC"},{"LHR","SFO"} };auto res = sln.findItinerary(tickets);Assert({ "JFK","MUC","LHR","SFO","SJC" }, res);}{Solution sln;tickets = { {"JFK","SFO"},{"JFK","ATL"},{"SFO","ATL"},{"ATL","JFK"},{"ATL","SFO"} };auto res = sln.findItinerary(tickets);Assert({ "JFK","ATL","JFK","SFO","ATL","SFO" }, res);}
}

2023年4月

class Solution {
public:vector<string> findItinerary(vector<vector<string>>& tickets) {		for (const auto& v : tickets){m_vNeiB[v[0]].emplace(v[1]);}dfs("JFK");std::reverse(m_vRet.begin(), m_vRet.end());return m_vRet;}void dfs(const string& sCur){while (m_vNeiB.count(sCur) && m_vNeiB[sCur].size()){const string sNext = m_vNeiB[sCur].top();m_vNeiB[sCur].pop();dfs(sNext);}m_vRet.emplace_back(sCur);}std::unordered_map < string, std::priority_queue<string, vector<string>, greater<string>>> m_vNeiB;vector<string> m_vRet;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

这篇关于【深度优先搜索】【图论】【推荐】332. 重新安排行程的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/759389

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

防近视护眼台灯什么牌子好?五款防近视效果好的护眼台灯推荐

在家里,灯具是属于离不开的家具,每个大大小小的地方都需要的照亮,所以一盏好灯是必不可少的,每个发挥着作用。而护眼台灯就起了一个保护眼睛,预防近视的作用。可以保护我们在学习,阅读的时候提供一个合适的光线环境,保护我们的眼睛。防近视护眼台灯什么牌子好?那我们怎么选择一个优秀的护眼台灯也是很重要,才能起到最大的护眼效果。下面五款防近视效果好的护眼台灯推荐: 一:六个推荐防近视效果好的护眼台灯的

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2431 poj 3253 优先队列的运用

poj 2431: 题意: 一条路起点为0, 终点为l。 卡车初始时在0点,并且有p升油,假设油箱无限大。 给n个加油站,每个加油站距离终点 l 距离为 x[i],可以加的油量为fuel[i]。 问最少加几次油可以到达终点,若不能到达,输出-1。 解析: 《挑战程序设计竞赛》: “在卡车开往终点的途中,只有在加油站才可以加油。但是,如果认为“在到达加油站i时,就获得了一

智能交通(二)——Spinger特刊推荐

特刊征稿 01  期刊名称: Autonomous Intelligent Systems  特刊名称: Understanding the Policy Shift  with the Digital Twins in Smart  Transportation and Mobility 截止时间: 开放提交:2024年1月20日 提交截止日

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大