当前位置: 首页 > news >正文

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[n1][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」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…...

学习笔记-接口测试(postman、jmeter)

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

如何高效批量查询快递单号,提高工作效率?

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

12万汉语源流词典汉字记性ACCESS\EXCEL数据库

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

深度解剖数据在队列的应用

> 作者简介&#xff1a;დ旧言~&#xff0c;目前大一&#xff0c;现在学习Java&#xff0c;c&#xff0c;c&#xff0c;Python等 > 座右铭&#xff1a;松树千年终是朽&#xff0c;槿花一日自为荣。 > 望小伙伴们点赞&#x1f44d;收藏✨加关注哟&#x1f495;&#x1…...

IMX6ULL移植篇-Linux内核源码目录分析二

一. Linux内核源码目录 本文继续来具体说明 Linux内核源码的一些重要文件含义。 本文续上一篇文章&#xff0c;地址如下&#xff1a; IMX6ULL移植篇-Linux内核源码目录分析一_凌肖战的博客-CSDN博客 二. Linux内核源码目录分析 9. init 目录 此目录存放 Linux 内核启动的…...

汽车行业数据治理方案,助力车企研产供销数据一体化

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

canvas-绘图库fabric.js简介

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

代码审计——任意文件下载详解(二)

为方便您的阅读&#xff0c;可点击下方蓝色字体&#xff0c;进行跳转↓↓↓ 01 漏洞描述02 审计要点03 漏洞特征04 漏洞案例05 修复方案 01 漏洞描述 网站可能提供文件查看或下载的功能&#xff0c;如果对用户查看或下载的文件不做限制&#xff0c;就能够查看或下载任意的文件&…...

19异常的学习笔记

异常 很重要&#xff0c;有利于我们平时处理问题 异常就是代表程序出现了问题 常见的异常比如说 数组越界除法除0 异常的体系是什么 java.lang.Throwable Error Exception RuntimeException 其他异常 Error 代表的是系统级别的错误&#xff0c;也就是一旦系统出现问题&…...

Jenkins学习笔记4

配置构建流程&#xff1a; Jenkins任务创建&#xff1a; 1&#xff09;创建新任务&#xff1a; 把这个Accept first connection改成 No Validation。问题得到解决。 构建触发器这块暂时没有需要配置的。 传输文件到nginx-server这个web服务器中。 将文件上传到/usr/share/n…...

自学 Java 需要具备哪些基本条件或技能?

新手初学者在自己学习Java时&#xff0c;需要注意两个方面&#xff0c;一个是学习方面&#xff0c;一个是知识点方面&#xff01; 学习方面&#xff1a; 1、做学习计划并保持自律 在我们学习Java的过程中&#xff0c;尽量减少干扰&#xff0c;把自己的全部注意力集中在Java上…...

[激光原理与应用-68]:如何消除50Hz工频干扰和差分信号应对工频干扰

目录 一、什么工频干扰 1.1 什么工频干扰 1.2 工频干扰的幅度 1.3 工频干扰如何进入设备 1.4 工频干扰的负面影响 二、如何消除工频干扰 2.1 要消除工频干扰&#xff0c;可以考虑以下方法&#xff1a; 2.2 要具体消除工频干扰&#xff0c;可以采取以下措施 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函数&#xff1a;定义、调用和主函数的完整指南 精通Java函数&#xff1a;定义、调用和主函数的完整指南摘要引言1. Java函数基础什么是Java函数&#xff1f;函数的定义和命名规则参数和返回值的概念 2. 函数的定义与语法如何声明和定义函数&#xff1f;函数的参数和参…...

springboot相关操作学习汇总

IDEAMAVEN apache maven 3.6.3 的安装及配置IntelliJ IDEA 安装及配置详细教程Maven下载安装及IDEA配置Maven的超详细教程 GIT 版本控制工具 - git的安装与使用gitlab上传新项目全过程 SPRINGBOOT IDEAmavenSpringboot工程创建超详细过程示例SpingBoot&#xff1a;整合Myb…...

如何在微信上制作自己的小程序卖东西

在当今的数字化时代&#xff0c;微信小程序已成为电商行业的重要平台。本文将详细解析电商微信小程序的制作流程&#xff0c;帮助你了解从零到上线的过程。 一、前期准备 1. 确定商城定位和目标群体&#xff1a;在制作电商微信小程序前&#xff0c;你需要明确商城的定位&#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、 字符级场景文本识别的实…...

从电大搜题到上海开放大学,广播电视大学引领学习新风尚

近年来&#xff0c;随着信息技术的飞速发展&#xff0c;互联网的普及和应用成为了我们生活中不可或缺的一部分。而在大学学习领域&#xff0c;电大搜题微信公众号应运而生&#xff0c;为广大学子提供了便捷的学习资源和交流平台。在这个信息高速发展的时代&#xff0c;上海开放…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

Opencv中的addweighted函数

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

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出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求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

实战三:开发网页端界面完成黑白视频转为彩色视频

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

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的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…...