每天一道leetcode:1129. 颜色交替的最短路径(图论中等广度优先遍历)
今日份题目:
给定一个整数 n,即有向图中的节点数,其中节点标记为 0 到 n - 1。图中的每条边为红色或者蓝色,并且可能存在自环或平行边。
给定两个数组 redEdges 和 blueEdges,其中:
-
redEdges[i] = [ai, bi]表示图中存在一条从节点ai到节点bi的红色有向边, -
blueEdges[j] = [uj, vj]表示图中存在一条从节点uj到节点vj的蓝色有向边。
返回长度为 n 的数组 answer,其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径,那么 answer[x] = -1。
示例1
输入:n = 3, red_edges = [[0,1],[1,2]], blue_edges = [] 输出:[0,1,-1]
示例2
输入:n = 3, red_edges = [[0,1]], blue_edges = [[2,1]] 输出:[0,1,-1]
提示
-
1 <= n <= 100 -
0 <= redEdges.length, blueEdges.length <= 400 -
redEdges[i].length == blueEdges[j].length == 2 -
0 <= ai, bi, uj, vj < n
题目思路
依旧是使用bfs广度优先遍历,详细过程可看代码中的注释。
本道题目主要是注意细节,比如三维表next、二维表dist等等。
代码
class Solution
{
public:vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {vector<vector<vector<int> > > next(2,vector<vector<int> >(n));for(auto &e:redEdges) {next[0][e[0]].push_back(e[1]);//第一个二维表存放红边信息}for(auto &e:blueEdges) {next[1][e[0]].push_back(e[1]);//第二个二维表存放蓝边信息}vector<vector<int> > dist(2,vector<int>(n,INT_MAX)); //两种类型的颜色最短路径的长度queue<pair<int, int> > p;dist[0][0]=0;dist[1][0]=0;p.push({0,0});//第一个表的0p.push({0,1});//第二个表的0while(!p.empty()) {int xy=p.front();p.pop();for(auto y:next[1-xy.second][xy.first]) //遍历当前点的邻接点{if(dist[1-xy.second][y]!=INT_MAX) //表示遍历过了{continue;}//实现交替路径dist[1-xy.second][y]=dist[xy.second][xy.first]+1;//另一个颜色的边数加一p.push({y,1-xy.second});}}vector<int> ans(n);for(int i=0;i<n;i++) {ans[i]=min(dist[0][i],dist[1][i]);//两个图中最小的路径长if(ans[i]==INT_MAX) //不存在,置为-1{ans[i]=-1;}}return ans;}
};
提交结果

欢迎大家在评论区讨论,如有不懂的代码部分,欢迎在评论区留言!
相关文章:
每天一道leetcode:1129. 颜色交替的最短路径(图论中等广度优先遍历)
今日份题目: 给定一个整数 n,即有向图中的节点数,其中节点标记为 0 到 n - 1。图中的每条边为红色或者蓝色,并且可能存在自环或平行边。 给定两个数组 redEdges 和 blueEdges,其中: redEdges[i] [ai, bi…...
原生js发送ajax请求---ajax请求篇(一)
在原生js中我们使用的是XMLHttpRequest对象来发送ajax请求 主要步骤就是: 1.创建XMLHTTPRequest对象 2.使用open方法设置和服务器的交互信息 3.设置发送的数据,开始和服务器端交互 4.注册事件 5.更新界面 (1) get方式 //步骤一…...
【ARM 嵌入式 编译系列 2.1 -- GCC 编译参数学习】
文章目录 1.1 GCC 编译参数1.1.1 GCC arm-noe-eabi- 介绍1.1.1.1 ARM 和 Thumb 指令集区别1.1.2 GCC CFLAGS 介绍1.1.3 GCC LDFLAGS 介绍1.1.4 CXXFLAGS 介绍上篇文章:ARM 嵌入式 编译系列 2 – GCC 编译过程介绍 下篇文章:ARM 嵌入式 C 入门及渐进 3 – GCC attribute((weak…...
C++教程 - How to C++系列专栏第3篇
关于专栏 这个专栏是优质的C教程专栏,如果你还没看过第0篇,点击C教程 - How to C系列专栏第0篇去第0篇 本专栏一致使用操作系统:macOS Ventura,代码编辑器:CLion,C编译器:Clang 感谢一路相伴…...
使用Edge和chrom扩展工具(GoFullPage)实现整页面截图或生成PDF文件
插件GoFullPage下载:点击免费下载 如果在浏览网页时,有需要整个页面截图或导出PDF文件的需求,这里分享一个Edge浏览器的扩展插件:GoFullPage。 这个工具可以一键实现页面从上到下滚动并截取。 一、打开“管理扩展”(…...
image has dependent child images
问题:很多none的镜像无法被删除 解决过程: 1、通过 docker image prune -f 提示可删除为 0 2、直接进行删除报错: docker rmi 8f5116cbc201Error response from daemon: conflict: unable to delete 8f5116cbc201 (cannot be forced) - im…...
Linux系统中基于NGINX的代理缓存配置指南
作为一名专业的爬虫程序员,你一定知道代理缓存在加速网站响应速度方面的重要性。而使用NGINX作为代理缓存服务器,能够极大地提高性能和效率。本文将为你分享Linux系统中基于NGINX的代理缓存配置指南,提供实用的解决方案,助你解决在…...
openCV项目开发实战--详细介绍如何改善夜间图像的照明(附python和C++源码)
文末附完整的代码实现下载链接 介绍 对于非摄影师来说,在光线不佳的条件下拍出好照片似乎很神奇。完成低光摄影需要技巧、经验和正确的设备的结合。在弱光下拍摄的图像缺乏色彩和独特的边缘。它们还遭受能见度差和深度未知的困扰。这些缺点使得此类图像不适合个人使用或图像处…...
rabbitmq的消息应答
消费者完成一个任务可能需要一段时间,如果其中一个消费者处理一个长的任务并仅只完成 了部分突然它挂掉了,会发生什么情况。RabbitMQ 一旦向消费者传递了一条消息,便立即将该消 息标记为删除。在这种情况下,突然有个消费者挂掉了…...
如何重置树莓派 Pico(重置外围设备失败)
有时候需要重置树莓派 Pico,一种方法是按住 Pico 上的“BOOTSEL”按钮再插入 USB;或者用按钮连接“RUN”和“GND”针脚,然后同时按下这个按钮和“BOOTSEL”按钮。这样就可以进入 USB 模式,这样从一定程度进行了重置。 但是这种方…...
LaWGPT基于中文法律知识的大语言模型_初步安装
准备代码,创建环境 # 下载代码 git clone gitgithub.com:pengxiao-song/LaWGPT.git cd LaWGPT# 创建环境 conda create -n lawgpt python3.10 -y conda activate lawgpt国内网络环境问题。你可以把requirements.txt里面的github.com替换成kgithub.com(这…...
一文学会sklearn中的交叉验证方法,cross_validate和KFlod实战案例
前言 在机器学习中,我们经常需要评估模型的性能。而为了准确评估模型的性能,我们需要使用一种有效的评估方法。五折交叉验证(5-fold cross-validation)就是其中一种常用的模型评估方法,用于评估机器学习模型的性能和泛…...
《面试1v1》ElasticSearch倒排索引
🍅 作者简介:王哥,CSDN2022博客总榜Top100🏆、博客专家💪 🍅 技术交流:定期更新Java硬核干货,不定期送书活动 🍅 王哥多年工作总结:Java学习路线总结…...
基于架构的软件开发方法
基于架构的软件开发方法 基于架构的软件开发方法是由架构驱动的,即指由构成体系结构的商业、质量和功能需求的组合驱动的。使用ABSD 方法,设计活动可以从项目总体功能框架明确就开始,这意味着需求抽取和分析还没有完成(甚至远远没有完成)&am…...
实战篇之基于二进制思想的用户标签系统(Mysql+SpringBoot)
一: 计算机中的二进制 计算机以二进制表示数据,以表示电路中的正反。在二进制下,一个位只有 0 和 1 。逢二进一 位。类似十进制下,一个位只有 0~9 。逢十进一位。 二: 进制常用运算 (位运算)…...
Ansible 进阶
Ansible 进阶 ⤴️Ansible 入门看这篇文章⤵️Ansible 实战看这篇文章 一.Ansible 中的 Playbook 1.1 Playbook 介绍 如下图,ansible 在整个管理过程中使用 playbook 的大体流程。 Playbook 中包含多个 role,每个 role 对应于在远程主机完成某个比较复…...
滴滴Ceph分布式存储系统优化之锁优化
摘自:https://mp.weixin.qq.com/s/oWujGOLLGItu1Bv5AuO0-A 2020-09-02 21:45 0.引言 Ceph是国际知名的开源分布式存储系统,在工业界和学术界都有着重要的影响。Ceph的架构和算法设计发表在国际系统领域顶级会议OSDI、SOSP、SC等上。Ceph社区得到Red Hat…...
flutter开发实战-MethodChannel实现flutter与iOS双向通信
flutter开发实战-MethodChannel实现flutter与iOS双向通信 最近开发中需要iOS与flutter实现通信,这里使用的MethodChannel 如果需要flutter与Android实现双向通信,请看 https://blog.csdn.net/gloryFlow/article/details/132218837 这部分与https://bl…...
华为、阿里巴巴、字节跳动 100+ Python 面试问题总结(七)
系列文章目录 个人简介:机电专业在读研究生,CSDN内容合伙人,博主个人首页 Python面试专栏:《Python面试》此专栏面向准备面试的2024届毕业生。欢迎阅读,一起进步!🌟🌟🌟 …...
K8S系列一:概念入门
写在前面 本文组织方式: K8S的架构、作用和目的。需要首先对K8S整体有所了解。 K8S是什么? 为什么是K8S? K8S怎么做? K8S的重要概念,即K8S的API对象。要学习和使用K8S必须知道和掌握的几个对象。 Pod 实例 Volume 数…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
Kafka主题运维全指南:从基础配置到故障处理
#作者:张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1:主题删除失败。常见错误2:__consumer_offsets占用太多的磁盘。 主题日常管理 …...
Leetcode33( 搜索旋转排序数组)
题目表述 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...
SpringAI实战:ChatModel智能对话全解
一、引言:Spring AI 与 Chat Model 的核心价值 🚀 在 Java 生态中集成大模型能力,Spring AI 提供了高效的解决方案 🤖。其中 Chat Model 作为核心交互组件,通过标准化接口简化了与大语言模型(LLM࿰…...
Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践
前言:本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中,跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南,你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案,并结合内网…...
机器学习的数学基础:线性模型
线性模型 线性模型的基本形式为: f ( x ) ω T x b f\left(\boldsymbol{x}\right)\boldsymbol{\omega}^\text{T}\boldsymbol{x}b f(x)ωTxb 回归问题 利用最小二乘法,得到 ω \boldsymbol{\omega} ω和 b b b的参数估计$ \boldsymbol{\hat{\omega}}…...
门静脉高压——表现
一、门静脉高压表现 00:01 1. 门静脉构成 00:13 组成结构:由肠系膜上静脉和脾静脉汇合构成,是肝脏血液供应的主要来源。淤血后果:门静脉淤血会同时导致脾静脉和肠系膜上静脉淤血,引发后续系列症状。 2. 脾大和脾功能亢进 00:46 …...
