每天一道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 数…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
