每天一道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 数…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
Vite中定义@软链接
在webpack中可以直接通过符号表示src路径,但是vite中默认不可以。 如何实现: vite中提供了resolve.alias:通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...
