LeetCode 2097. 合法重新排列数对【欧拉通路,DFS】2650
本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。
为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。
由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。
给你一个下标从 0 开始的二维整数数组 pairs
,其中 pairs[i] = [starti, endi]
。如果 pairs
的一个重新排列,满足对每一个下标 i
( 1 <= i < pairs.length
)都有 endi-1 == starti
,那么我们就认为这个重新排列是 pairs
的一个 合法重新排列 。
请你返回 任意一个 pairs
的合法重新排列。
注意: 数据保证至少存在一个 pairs
的合法重新排列。
示例 1:
输入:pairs = [[5,1],[4,5],[11,9],[9,4]]
输出:[[11,9],[9,4],[4,5],[5,1]]
解释:
输出的是一个合法重新排列,因为每一个 endi-1 都等于 starti 。
end0 = 9 == 9 = start1
end1 = 4 == 4 = start2
end2 = 5 == 5 = start3
示例 2:
输入:pairs = [[1,3],[3,2],[2,1]]
输出:[[1,3],[3,2],[2,1]]
解释:
输出的是一个合法重新排列,因为每一个 endi-1 都等于 starti 。
end0 = 3 == 3 = start1
end1 = 2 == 2 = start2
重新排列后的数组 [[2,1],[1,3],[3,2]] 和 [[3,2],[2,1],[1,3]] 都是合法的。
示例 3:
输入:pairs = [[1,2],[1,3],[2,1]]
输出:[[1,2],[2,1],[1,3]]
解释:
输出的是一个合法重新排列,因为每一个 endi-1 都等于 starti 。
end0 = 2 == 2 = start1
end1 = 1 == 1 = start2
提示:
1 <= pairs.length <= 10^5
pairs[i].length == 2
0 <= starti, endi <= 10^9
starti != endi
pairs
中不存在一模一样的数对。- 至少 存在 一个合法的
pairs
重新排列。
解法 欧拉路径+DFS
如果我们把数组 p a i r s pairs pairs 中出现的每个数看成一个节点, ( start i , end i ) (\textit{start}_i, \textit{end}_i) (starti,endi) 看成从 start i \textit{start}_i starti 到 end i \textit{end}_i endi 的一条有向边,那么 p a i r s pairs pairs 的一个合法排列就对应着:
- 从节点 pairs [ 0 ] [ 0 ] \textit{pairs}[0][0] pairs[0][0] 开始;
- 依次经过 pairs [ 0 ] [ 1 ] , pairs [ 1 ] [ 1 ] , ⋯ , pairs [ n − 1 ] [ 1 ] \textit{pairs}[0][1], \textit{pairs}[1][1], \cdots, \textit{pairs}[n-1][1] pairs[0][1],pairs[1][1],⋯,pairs[n−1][1]
的一条路径,其中 n n n 是数组 p a i r s pairs pairs 的长度。这条路径经过了图上的每一条边恰好一次,是一条「欧拉通路」,因此我们的目标就是找出图上的任意一条欧拉通路。
对于本题而言,首先需要找到欧拉通路的起始节点:
- 如果图中所有节点的入度和出度都相等,那么从任意节点开始都存在欧拉通路;
- 如果图中存在一个节点的出度比入度恰好多 1 1 1 ,另一个节点的入度恰好比出度多 1 1 1 ,那么欧拉通路必须从前一个节点开始,到后一个节点结束。
- 除此之外的有向图都不存在欧拉通路。
本题保证了至少存在一个合法排列,因此图已经是上述的两种情况之一。当我们确定起始节点后,就可以使用DFS求解欧拉通路了。如果我们得到的欧拉通路为:
v 1 , v 2 , v 3 , ⋯ , v n , v n + 1 v_1, v_2, v_3, \cdots, v_n, v_{n+1} v1,v2,v3,⋯,vn,vn+1
那么 [ [ v 1 , v 2 ] , [ v 2 , v 3 ] , ⋯ , [ v n , v n + 1 ] ] [[v_1, v_2], [v_2, v_3], \cdots, [v_n, v_{n+1}]] [[v1,v2],[v2,v3],⋯,[vn,vn+1]] 就是一个合法排列。
class Solution {
public:vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {// 存储图unordered_map<int, vector<int>> edges;// 存储入度和出度unordered_map<int, int> deg;for (const auto& p: pairs) {edges[p[0]].push_back(p[1]);++deg[p[0]], --deg[p[1]];}// 深度优先搜索(Hierholzer算法)求解欧拉通路vector<vector<int>> ans;function<void(int)> dfs = [&](int u) {while (!edges[u].empty()) {int v = edges[u].back();edges[u].pop_back(); // 删除一条边dfs(v);ans.push_back({u, v});}}; // 寻找起始节点for (const auto& [x, occ]: deg) // 如果有节点出度比入度恰好多 1,那么只有它才能是起始节点if (occ == 1) {dfs(x);break;}if (ans.empty()) dfs(pairs[0][0]);reverse(ans.begin(), ans.end());return ans;}
};
复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n) ,其中 nnn 是数组 p a i r s pairs pairs 的长度。图中有不超过 n + 1 n+1 n+1 个节点和 n n n 条边,因此求解欧拉通路需要的时间为 O ( n ) O(n) O(n) 。
- 空间复杂度: O ( n ) O(n) O(n) ,即为存储图需要使用的空间。
求解欧拉通路使用DFS,可以参考「OI Wiki — 欧拉图」 ,一般使用 Hierholzer \text{Hierholzer} Hierholzer 算法求解欧拉通路,与欧拉回路或欧拉通路有关的题目:
- 「332. 重新安排行程」
- 「753. 破解保险箱」
相关文章:
LeetCode 2097. 合法重新排列数对【欧拉通路,DFS】2650
本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章…...

学习笔记-接口测试(postman、jmeter)
目录 一、什么是接口测试 二、前端和后端 三、get请求和post请求的区别 四、cookie和session 五、接口测试的依据 六、HTTP状态码 七、通用接口用例 八、postman接口测试 九、Jmeter接口测试 一、什么是接口测试 通常做的接口测试指的是系统对外的接口,比…...

如何高效批量查询快递单号,提高工作效率?
在日常生活中,快递单号的查询是一项常规任务。过去,这项任务需要通过人工一个一个地在快递平台上查询,既耗时又费力。然而,随着科技的发展,我们有了更多的工具可以帮助我们高效地完成这项任务。本文将介绍如何使用固乔…...

12万汉语源流词典汉字记性ACCESS\EXCEL数据库
《12万汉语源流词典汉字记性ACCESS数据库》在继承前人经验的基础上,注意吸收今人的研究成果,注重形音义的密切配合,尽可能历史地、正确地反映汉字形音义的发展。在字形方面,简要说明其结构的演变。语义解释遵循古今语义的发展变化…...

深度解剖数据在队列的应用
> 作者简介:დ旧言~,目前大一,现在学习Java,c,c,Python等 > 座右铭:松树千年终是朽,槿花一日自为荣。 > 望小伙伴们点赞👍收藏✨加关注哟💕…...
IMX6ULL移植篇-Linux内核源码目录分析二
一. Linux内核源码目录 本文继续来具体说明 Linux内核源码的一些重要文件含义。 本文续上一篇文章,地址如下: IMX6ULL移植篇-Linux内核源码目录分析一_凌肖战的博客-CSDN博客 二. Linux内核源码目录分析 9. init 目录 此目录存放 Linux 内核启动的…...

汽车行业数据治理方案,助力车企研产供销数据一体化
随着数字技术的不断革新和应用,汽车行业已转向大数据、新技术寻求生产力突破,以电动化、网联化、智能化、共享化为标志的“汽车新四化”,为汽车行业带来了翻天覆地的变化。如何抓住“新四化”的机会,在汽车产业变革中赢得先机&…...

canvas-绘图库fabric.js简介
一般情况下简单的绘制,其实canvas原生方法也可以满足,比如画个线,绘制个圆形、正方形、加个文案。 let canvas document.getElementById(canvas);canvas.width 1200;canvas.height 600;canvas.style.width 1200px;canvas.style.height 6…...

代码审计——任意文件下载详解(二)
为方便您的阅读,可点击下方蓝色字体,进行跳转↓↓↓ 01 漏洞描述02 审计要点03 漏洞特征04 漏洞案例05 修复方案 01 漏洞描述 网站可能提供文件查看或下载的功能,如果对用户查看或下载的文件不做限制,就能够查看或下载任意的文件&…...
19异常的学习笔记
异常 很重要,有利于我们平时处理问题 异常就是代表程序出现了问题 常见的异常比如说 数组越界除法除0 异常的体系是什么 java.lang.Throwable Error Exception RuntimeException 其他异常 Error 代表的是系统级别的错误,也就是一旦系统出现问题&…...

Jenkins学习笔记4
配置构建流程: Jenkins任务创建: 1)创建新任务: 把这个Accept first connection改成 No Validation。问题得到解决。 构建触发器这块暂时没有需要配置的。 传输文件到nginx-server这个web服务器中。 将文件上传到/usr/share/n…...
自学 Java 需要具备哪些基本条件或技能?
新手初学者在自己学习Java时,需要注意两个方面,一个是学习方面,一个是知识点方面! 学习方面: 1、做学习计划并保持自律 在我们学习Java的过程中,尽量减少干扰,把自己的全部注意力集中在Java上…...

[激光原理与应用-68]:如何消除50Hz工频干扰和差分信号应对工频干扰
目录 一、什么工频干扰 1.1 什么工频干扰 1.2 工频干扰的幅度 1.3 工频干扰如何进入设备 1.4 工频干扰的负面影响 二、如何消除工频干扰 2.1 要消除工频干扰,可以考虑以下方法: 2.2 要具体消除工频干扰,可以采取以下措施 2.3 使用差…...

【力扣-每日一题】LCP 06. 拿硬币
class Solution { public:int minCount(vector<int>& coins) {int res0;for(auto i:coins){resi/2;res(i%2)?1:0;}return res;} };...

【JAVA-Day32】精通Java函数:定义、调用和主函数的完整指南
精通Java函数:定义、调用和主函数的完整指南 精通Java函数:定义、调用和主函数的完整指南摘要引言1. Java函数基础什么是Java函数?函数的定义和命名规则参数和返回值的概念 2. 函数的定义与语法如何声明和定义函数?函数的参数和参…...
springboot相关操作学习汇总
IDEAMAVEN apache maven 3.6.3 的安装及配置IntelliJ IDEA 安装及配置详细教程Maven下载安装及IDEA配置Maven的超详细教程 GIT 版本控制工具 - git的安装与使用gitlab上传新项目全过程 SPRINGBOOT IDEAmavenSpringboot工程创建超详细过程示例SpingBoot:整合Myb…...

如何在微信上制作自己的小程序卖东西
在当今的数字化时代,微信小程序已成为电商行业的重要平台。本文将详细解析电商微信小程序的制作流程,帮助你了解从零到上线的过程。 一、前期准备 1. 确定商城定位和目标群体:在制作电商微信小程序前,你需要明确商城的定位&#x…...

24.Xaml ListView控件-----显示数据
1.运行效果 2.运行源码 a.Xaml源码 <Window x:Class="testView.MainWindow"xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d="http://schemas.mic…...
YoloV5改进实战:使用MPDIoU改进YoloV5
文章目录 摘要论文:揭秘精准高效的MPDIoU损失函数摘要1、简介2、相关工作2.1、目标检测和实例分割2.2. 场景文本识别2.3、边界框回归的损失函数3、点距最小的并集交点4、实验结果4.1、 实验设置4.2、数据集4.3、 评估协议4.4、 目标检测的实验结果4.5、 字符级场景文本识别的实…...
从电大搜题到上海开放大学,广播电视大学引领学习新风尚
近年来,随着信息技术的飞速发展,互联网的普及和应用成为了我们生活中不可或缺的一部分。而在大学学习领域,电大搜题微信公众号应运而生,为广大学子提供了便捷的学习资源和交流平台。在这个信息高速发展的时代,上海开放…...

Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...

Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...

剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...

【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...

实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...

通过MicroSip配置自己的freeswitch服务器进行调试记录
之前用docker安装的freeswitch的,启动是正常的, 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...
vue3 daterange正则踩坑
<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...