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

LeetCode-2608. 图中的最短环【广度优先搜索 图,腾讯面试真题】

LeetCode-2608. 图中的最短环【广度优先搜索 图,腾讯面试真题】

  • 题目描述:
  • 解题思路一:【一图秒懂】枚举起点跑 BFS
  • 解题思路二:背诵版
  • 解题思路三:

题目描述:

现有一个含 n 个顶点的 双向 图,每个顶点按从 0 到 n - 1 标记。图中的边由二维整数数组 edges 表示,其中 edges[i] = [ui, vi] 表示顶点 ui 和 vi 之间存在一条边。每对顶点最多通过一条边连接,并且不存在与自身相连的顶点。

返回图中 最短 环的长度。如果不存在环,则返回 -1 。

环 是指以同一节点开始和结束,并且路径中的每条边仅使用一次。

示例 1:
在这里插入图片描述
输入:n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]
输出:3
解释:长度最小的循环是:0 -> 1 -> 2 -> 0

示例 2:
在这里插入图片描述
输入:n = 4, edges = [[0,1],[0,2]]
输出:-1
解释:图中不存在循环

提示:

2 <= n <= 1000
1 <= edges.length <= 1000
edges[i].length == 2
0 <= ui, vi < n
ui != vi
不存在重复的边

解题思路一:【一图秒懂】枚举起点跑 BFS

题解参考
在这里插入图片描述
问:为什么说发现一个已经入队的点,就说明有环?

答:这说明到同一个点有两条不同的路径,这两条路径组成了一个环。

class Solution:def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:g = [[] for _ in range(n)]for x, y in edges:g[x].append(y)g[y].append(x) # 建图def bfs(start):ans = infdis = [-1] * n # dis[i] 表示从start到i的最短路径长度dis[start] = 0q = deque([(start, -1)])while q:x, fa = q.popleft()for y in g[x]:if dis[y] < 0: # 第一次遇到dis[y] = dis[x] + 1q.append((y, x))elif y != fa: # 第二次遇到ans = min(ans, dis[x] + dis[y] + 1)return ansans = min(bfs(i) for i in range(n))return ans if ans < inf else -1

时间复杂度:O(nm)
空间复杂度:O(n+m)

解题思路二:背诵版

class Solution:def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:g = [[] for _ in range(n)]for u, v in edges:g[u].append(v)g[v].append(u)def bfs(start):ans = infdis = [-1] * nq = deque([(start, -1)])dis[start] = 0while q:x, fa = q.popleft()for y in g[x]:if dis[y] < 0:dis[y] = dis[x] + 1q.append((y, x))elif y != fa:ans = min(ans, dis[x] + dis[y] + 1)return ansans = min(bfs(i) for i in range(n))return ans if ans < inf else -1

时间复杂度:O(nm)
空间复杂度:O(n+m)

解题思路三:


时间复杂度:O(n)
空间复杂度:O(n)


创作不易,观众老爷们请留步… 动起可爱的小手,点个赞再走呗 (๑◕ܫ←๑)
欢迎大家关注笔者,你的关注是我持续更博的最大动力


原创文章,转载告知,盗版必究



在这里插入图片描述


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

相关文章:

LeetCode-2608. 图中的最短环【广度优先搜索 图,腾讯面试真题】

LeetCode-2608. 图中的最短环【广度优先搜索 图&#xff0c;腾讯面试真题】 题目描述&#xff1a;解题思路一&#xff1a;【一图秒懂】枚举起点跑 BFS解题思路二&#xff1a;背诵版解题思路三&#xff1a; 题目描述&#xff1a; 现有一个含 n 个顶点的 双向 图&#xff0c;每个…...

IDEA 编译报错 “java: 常量字符串过长” 的解决办法

目录 一、问题描述二、问题原因2.1 理论角度2.2 源码角度 三、解决方案解决方案①&#xff1a;StringBuilder 拼接解决方案②&#xff1a;读取文件内容 四、方案验证 在线文本换行工具&#xff1a; https://lzltool.cn/Toolkit/WrapWordsInText 一、问题描述 今天在开发过程中…...

RK3568平台开发系列讲解(I2C篇)I2C 总线实现 client 设备方法

🚀返回专栏总目录 文章目录 一、非设备树实现 i2c client1.1、i2c_new_device1.2、i2c client二、设备树实现 i2c2.1、i2c_client 结构体的生成2.2、i2c_driver 驱动2.2.1、module_i2c_driver2.2.2、fan53555_regulator_probe沉淀、分享、成长,让自己和他人都能有所收获!�…...

K8S安装和部署

环境部署说明 主机IPmaster172.25.254.100node10172.25.254.10node20172.25.254.20harbor172.25.254.233 所有节点禁用selinux和防火墙 所有节点同步时间和解析 所有节点安装docker-ce 所有节点禁用swap&#xff0c;注意注释掉/etc/fstab文件中的定义 解析配置&#xff08;…...

Singleton(单例模式)

1. 意图 在开发中&#xff0c;若某些模块或功能只需要一个类实例&#xff0c;所有调用地方通过着一个类对象访问功能&#xff0c;单例模式符合这种类实例创建模式&#xff0c;并且通过提供统一类实例接口访问类对象。 2. 适用性 《Gof 设计模式-可复用面向对象软件的基础》中对…...

【Linux报错】“-bash: cd: too many arguments“

问题描述 今天使用 cd 想要调整某个文件目录时&#xff0c;发现以下报错 原因分析&#xff1a; arguments 是参数的意思&#xff0c;该报错提示参数过多&#xff0c;意味着系统识别到了多余参数 本质原因&#xff1a;你的命令中输入了多余的 ”空格“ &#xff0c;检查一…...

C# WebService返回参数为DataTable报错“XML文档有错误”

该问题由于DataTable列存在自定义类型。 解决该报错需要以下几步&#xff1a; 1、自定义类型增加xml序列化 2、由于C#从 XML 反序列化 DataSet 或 DataTable 时的默认限制&#xff0c;所以需要先把调用方的项目开放限制&#xff0c;如果是.netframework项目&#xff0c;需要…...

[paddle]paddleseg快速开始

快速开始 为了让大家快速了解PaddleSeg&#xff0c;本文档使用一个简单示例进行演示。在实际业务中&#xff0c;建议大家根据实际情况进行调整适配。 在开始下面示例之前&#xff0c;请大家确保已经安装好PaddleSeg开发环境&#xff08;安装说明&#xff09;。 1 准备数据 …...

UNIAPP popper气泡弹层【unibest框架下】vue3+typescript

看了下市场的代码&#xff0c;要么写的不怎么好&#xff0c;要么过于复杂。于是把市场的代码下下来了自己改。200行代码撸了个弹出层组件。兼容H5和APP。 功能&#xff1a; 1)只支持上下左右4个方向的弹层不支持侧边靠齐 2)不对屏幕边界适配 3)支持弹层外边点击自动隐藏 4)支持…...

launcher.py: error: the following arguments are required: --output_dir

记录一个LLaMA-Factroy配置过程。 安装 git clone --depth 1 https://github.com/hiyouga/LLaMA-Factory.git cd LLaMA-Factory pip install -e ".[torch,metrics]"训练 CUDA_VISIBLE_DEVICES0 llamafactory-cli train example/train_lora/.yaml按理说配置好文件应…...

C语言基础之结构体

今天我们来讲讲C语言基础的最后一个知识点了 —— 结构体。不知道大家对前面的C语言基础的知识点掌握的怎么样了呢&#xff1f;下面我们就开始讲解结构体的相关知识点吧&#xff01; 什么是结构体呢&#xff1f;或者说结构体有什么作用呢&#xff1f;对于复杂对象来说&#xff…...

Redis入门第四步:Redis发布与订阅

欢迎继续跟随《Redis新手指南&#xff1a;从入门到精通》专栏的步伐&#xff01;在本文中&#xff0c;我们将深入探讨Redis的发布与订阅&#xff08;Pub/Sub&#xff09;模式。这是一种强大的消息传递机制&#xff0c;适用于各种实时通信场景&#xff0c;如聊天应用、实时通知和…...

MySQL 之权限与授权

MySQL 权限及授权系统用于控制数据库用户对数据库资源的访问和操作权限。它提供了一种细粒度的安全控制机制&#xff0c;确保只有被授权的用户才能执行特定的操作。MySQL 的权限控制体系非常灵活&#xff0c;支持多种权限类型及级别&#xff08;数据库、表、列、存储过程等&…...

解决方案:Pandas里面的loc跟iloc,有什么区别

文章目录 一、现象二、解决方案案例使用loc使用iloc 简单总结 一、现象 在用Pandas库处理数据的时候&#xff0c;久而久之不用loc跟iloc&#xff0c;难免会有些混乱记混 二、解决方案 在Pandas中&#xff0c;loc和iloc是两种常用的数据选择方法&#xff0c;它们的主要区别在…...

C# 和 C++ 混合编程

以下是一个关于 C# 和 C 混合编程 的教程详细目录&#xff0c;涵盖了混合编程中的各个重要方面&#xff1a; 目录 1. 引言 1.1 什么是混合编程&#xff1f; 1.2 为什么选择 C# 和 C 进行混合编程&#xff1f; 1.3 应用场景和优势 2. 基本概念 2.1 C# 和 C 的基础差异 2.…...

Vxe UI vue vxe-table 实现表格单元格选中功能

Vxe UI vue vxe-table 实现表格单元格选中功能 在表格中实现鼠标点击任意单元格&#xff0c;选取的功能&#xff0c;通过 mouse-config 配置就可以开启单选功能&#xff0c;多选单元格选取功能需安装插件支持。 代码 参数说明 mouse-config 鼠标配置项&#xff1a; selected&…...

组合模式详解

1、组合模式基本介绍 1) 组合模式&#xff08;Composite Pattern&#xff09;&#xff0c;又叫部分整体模式&#xff0c;它创建了对象组的树形结构&#xff0c;将对象组合成树状结构以 表示“整体-部分”的层次关系。 2) 组合模式依据树形结构来组合对象&#xff0c;用来表示部…...

AltiumDesigner脚本开发-DIP封装制作

1.点击工具栏的运行工具(蓝色向右三角图标)可以执行脚本程序&#xff1b; 2.点击菜单栏Run->Run可以执行脚本程序&#xff1b; 3.在脚本编辑器中&#xff0c;按键盘的F9键可以执行脚本程序&#xff1b; 4.通过菜单栏执行脚本程序&#xff08;需要将程序添加到菜单栏中&am…...

乌班图基础设施安装之Mysql8.0+Redis6.X安装

简介&#xff1a;云服务器基础设施安装之 Mysql8.0Redis6.X 安装 Docker安装 # 按照依赖 yum install -y yum-utils device-mapper-persistent data lvm2 Docker Mirror 从去年开始. hub.docker.com[1] 在国内的访问速度极慢. 当时大家主要还是依赖国内的一些镜像源: 如中科…...

【动态规划-最长递增子序列(LIS)】力扣673.最长递增子序列的个数

给定一个未排序的整数数组 nums &#xff0c; 返回最长递增子序列的个数 。 注意 这个数列必须是 严格 递增的。 示例 1: 输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列&#xff0c;分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。 示例 2: 输入: [2,2,2,2,2] 输出: 5 解释:…...

SPM12实战:手把手教你搞定fMRI数据预处理(从时间矫正到空间平滑)

SPM12实战&#xff1a;零基础入门fMRI数据预处理全流程解析 第一次接触功能磁共振成像&#xff08;fMRI&#xff09;数据分析时&#xff0c;面对SPM12复杂的界面和晦涩的术语&#xff0c;很多新手都会感到无从下手。这篇文章将带你从零开始&#xff0c;用最直观的方式掌握fMRI数…...

农业遥感避坑指南:用大疆P4M多光谱数据生成NDVI,选智图还是Metashape?

农业遥感实战&#xff1a;大疆P4M多光谱数据NDVI生成工具选型指南 站在农田边缘&#xff0c;手持大疆精灵4多光谱版&#xff08;P4M&#xff09;遥控器的你&#xff0c;刚刚完成了一次作物长势监测飞行。无人机带回的宝贵数据&#xff0c;正等待转化为直观的NDVI图——这张&quo…...

GLM-OCR在跨境电商中的应用:多语言商品说明书OCR→自动翻译预处理

GLM-OCR在跨境电商中的应用&#xff1a;多语言商品说明书OCR→自动翻译预处理 1. 项目概述与背景 跨境电商卖家经常面临一个共同难题&#xff1a;来自不同国家的商品说明书语言各异&#xff0c;手动翻译不仅耗时耗力&#xff0c;还容易出错。传统OCR工具虽然能识别文字&#…...

肿瘤免疫微环境解析:8大免疫浸润工具实战指南

1. 肿瘤免疫微环境分析的核心价值 当你拿到一份肿瘤样本的转录组数据时&#xff0c;最令人兴奋的莫过于揭开它的免疫面纱——那些隐藏在肿瘤组织中的免疫细胞究竟在做什么&#xff1f;这就是免疫浸润分析的价值所在。想象一下&#xff0c;肿瘤组织就像一座复杂的城市&#xff0…...

当生物黑客入侵脑机接口:安全测试救了我们公司

在脑机接口&#xff08;Brain-Computer Interface, BCI&#xff09;技术飞速发展的今天&#xff0c;软件测试从业者正面临前所未有的安全挑战。作为一名资深测试工程师&#xff0c;我亲历了一场惊心动魄的生物黑客入侵事件——一场针对我们公司脑机接口产品的攻击险些导致灾难性…...

ESP32开发环境:VS Code与ESP-IDF插件高效配置指南

1. 为什么选择VS Code开发ESP32&#xff1f; 第一次接触ESP32开发时&#xff0c;我尝试过各种开发工具&#xff1a;Arduino IDE、PlatformIO、Eclipse...最后发现VS Code配合ESP-IDF插件才是最佳组合。这个方案不仅免费开源&#xff0c;更重要的是能充分发挥ESP32的全部性能特…...

实践指南:运用语义熵为LLM生成内容构建“幻觉防火墙”

1. 什么是语义熵&#xff1f;为什么它能成为LLM的"幻觉防火墙"&#xff1f; 第一次听到"语义熵"这个词时&#xff0c;我正被一个智能客服项目折磨得焦头烂额。当时我们的GPT-3.5模型总喜欢给用户编造不存在的产品功能&#xff0c;就像个过度热情的销售员。…...

基于python的演唱会抢票系统

目录同行可拿货,招校园代理 ,本人源头供货商核心功能模块技术实现要点扩展功能设计异常处理方案项目技术支持源码获取详细视频演示 &#xff1a;文章底部获取博主联系方式&#xff01;同行可合作同行可拿货,招校园代理 ,本人源头供货商 核心功能模块 用户管理模块 注册/登录功…...

SQLite在线查看器:浏览器中的数据库管理革命

SQLite在线查看器&#xff1a;浏览器中的数据库管理革命 【免费下载链接】sqlite-viewer View SQLite file online 项目地址: https://gitcode.com/gh_mirrors/sq/sqlite-viewer 在数据驱动的时代&#xff0c;SQLite数据库无处不在——从移动应用到桌面软件&#xff0c;…...

Tencent Hunyuan3D-1.0学术合作机会:腾讯混元团队的研究方向与合作模式

Tencent Hunyuan3D-1.0学术合作机会&#xff1a;腾讯混元团队的研究方向与合作模式 【免费下载链接】Hunyuan3D-1 腾讯开源的Hunyuan3D-1项目&#xff0c;创新提出两阶段3D生成方法&#xff0c;实现快速、高质量的文本到3D和图像到3D转换&#xff0c;融合Hunyuan-DiT模型&#…...