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

【Py/Java/C++三种语言详解】LeetCode743、网络延迟时间【单源最短路问题Djikstra算法】

可上 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳 od1441了解算法冲刺训练(备注【CSDN】否则不通过)

文章目录

  • 相关推荐阅读
    • 一、题目描述
    • 二、题目解析
    • 三、参考代码
      • Python
      • Java
      • C++
    • 时空复杂度
  • 华为OD算法/大厂面试高频题算法练习冲刺训练

相关推荐阅读

  • Dijkstra算法的具体介绍详见单源最短路问题:Dijkstra算法详解【经典算法,限时免费】)

一、题目描述

题目链接:https://leetcode.cn/problems/network-delay-time/description/

n 个网络节点,标记为 1n

给你一个列表 times,表示信号经过 有向 边的传递时间。 times[i] = (u(i), v(i), w(i)),其中 u(i) 是源节点,v(i) 是目标节点, w(i) 是一个信号从源节点传递到目标节点的时间。

现在,从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号?如果不能使所有节点收到信号,返回 -1

示例 1

在这里插入图片描述

输入:times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出:2

示例 2

输入:times = [[1,2,1]], n = 2, k = 1
输出:1

示例 3

输入:times = [[1,2,1]], n = 2, k = 2
输出:-1

提示

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= u(i), v(i) <= n
  • u(i) != v(i)
  • 0 <= w(i) <= 100
  • 所有 (u(i), v(i)) 对都 互不相同(即,不含重复边)

二、题目解析

题目要求计算从源点出发到达所有其他节点的最短路径,在所有最短路径中找到最大值。

所以这是一个单源最短路问题,可以使用Dijkstra算法来解决,计算出dist数组之后取最大值即可。

Dijkstra算法的具体介绍详见单源最短路问题:Dijkstra算法详解【经典算法,限时免费】)

三、参考代码

Python

INF = 100000  # 用于表示一个非常大的数,作为初始的最短距离class Solution:def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:# 创建一个邻接表,用于存储每个节点的相邻节点及对应的路径权重neighbor_dic = defaultdict(list)for a, b, w in times:# 将边 (a -> b) 和对应的权重 w 加入邻接表neighbor_dic[a].append((b, w))  # 初始化一个列表 dist,用于记录从源节点 k 到每个节点的最短距离# 初始时,所有节点的距离都设置为 INF(表示尚未访问或不可达)dist = [INF] * (n+1)# 初始化一个最小堆,用于在Dijkstra算法中提取当前已知最短路径的节点# 堆中元素是 (当前时间, 当前节点) 元组heap = [(0, k)]# 进行Dijkstra(类似BFS)while heap:# 从堆中弹出当前时间最小的节点cur_time, cur_node = heappop(heap)# 如果当前节点的已记录最短时间比当前时间更小,说明已经找到更优的路径# 因此可以跳过当前节点if cur_time > dist[cur_node]:continue# 更新从源节点 k 到当前节点的最短时间dist[cur_node] = cur_time# 遍历当前节点的所有相邻节点for next_node, next_weight in neighbor_dic[cur_node]:# 计算通过当前节点到达相邻节点所需的时间next_time = cur_time + next_weight# 如果通过当前节点到达相邻节点的时间比之前记录的最短时间更短# 则更新相邻节点的最短时间,并将其加入堆中以便进一步探索if next_time < dist[next_node]:heappush(heap, (next_time, next_node))# 找到从源节点 k 到所有节点的最短路径中的最大值ans = max(dist[1:])# 如果最大值小于 INF,说明所有节点都可达,返回最大值作为网络延迟时间# 否则返回 -1,表示有节点无法到达return ans if ans < INF else -1

Java

import java.util.*;class Solution {static final int INF = 100000;  // 用于表示一个非常大的数,作为初始的最短距离public int networkDelayTime(int[][] times, int n, int k) {// 创建一个邻接表,用于存储每个节点的相邻节点及对应的路径权重Map<Integer, List<int[]>> neighbor_dic = new HashMap<>();for (int i = 1; i <= n; i++) {neighbor_dic.put(i, new ArrayList<>());}for (int[] time : times) {int a = time[0], b = time[1], w = time[2];// 将边 (a -> b) 和对应的权重 w 加入邻接表neighbor_dic.get(a).add(new int[]{b, w});}// 初始化一个数组 dist,用于记录从源节点 k 到每个节点的最短距离// 初始时,所有节点的距离都设置为 INF(表示尚未访问或不可达)int[] dist = new int[n + 1];Arrays.fill(dist, INF);dist[k] = 0;  // 源节点到自己的距离为0// 初始化一个最小堆,用于在Dijkstra算法中提取当前已知最短路径的节点// 堆中元素是 (当前时间, 当前节点) 元组PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));heap.offer(new int[]{0, k});// 进行Dijkstra(类似BFS)while (!heap.isEmpty()) {// 从堆中弹出当前时间最小的节点int[] cur = heap.poll();int cur_time = cur[0], cur_node = cur[1];// 如果当前节点的已记录最短时间比当前时间更小,说明已经找到更优的路径// 因此可以跳过当前节点if (cur_time > dist[cur_node]) {continue;}// 遍历当前节点的所有相邻节点for (int[] neighbor : neighbor_dic.getOrDefault(cur_node, new ArrayList<>())) {int next_node = neighbor[0], next_weight = neighbor[1];// 计算通过当前节点到达相邻节点所需的时间int next_time = cur_time + next_weight;// 如果通过当前节点到达相邻节点的时间比之前记录的最短时间更短// 则更新相邻节点的最短时间,并将其加入堆中以便进一步探索if (next_time < dist[next_node]) {dist[next_node] = next_time;heap.offer(new int[]{next_time, next_node});}}}// 找到从源节点 k 到所有节点的最短路径中的最大值int ans = Arrays.stream(dist).skip(1).max().getAsInt();// 如果最大值小于 INF,说明所有节点都可达,返回最大值作为网络延迟时间// 否则返回 -1,表示有节点无法到达return ans < INF ? ans : -1;}
}

C++

int INF = 100000;  // 用于表示一个非常大的数,作为初始的最短距离class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {// 创建一个邻接表,用于存储每个节点的相邻节点及对应的路径权重unordered_map<int, vector<pair<int, int>>> neighbor_dic;for (const auto& time : times) {int a = time[0], b = time[1], w = time[2];// 将边 (a -> b) 和对应的权重 w 加入邻接表neighbor_dic[a].push_back({b, w});}// 初始化一个列表 dist,用于记录从源节点 k 到每个节点的最短距离// 初始时,所有节点的距离都设置为 INF(表示尚未访问或不可达)vector<int> dist(n + 1, INF);dist[k] = 0;  // 起点距离为0// 初始化一个最小堆,用于在Dijkstra算法中提取当前已知最短路径的节点// 堆中元素是 (当前时间, 当前节点) 元组priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;heap.push({0, k});// 进行Dijkstra算法(类似BFS)while (!heap.empty()) {// 从堆中弹出当前时间最小的节点auto [cur_time, cur_node] = heap.top();heap.pop();// 如果当前节点的已记录最短时间比当前时间更小,说明已经找到更优的路径// 因此可以跳过当前节点if (cur_time > dist[cur_node]) {continue;}// 遍历当前节点的所有相邻节点for (auto& [next_node, next_weight] : neighbor_dic[cur_node]) {// 计算通过当前节点到达相邻节点所需的时间int next_time = cur_time + next_weight;// 如果通过当前节点到达相邻节点的时间比之前记录的最短时间更短// 则更新相邻节点的最短时间,并将其加入堆中以便进一步探索if (next_time < dist[next_node]) {dist[next_node] = next_time;heap.push({next_time, next_node});}}}// 找到从源节点 k 到所有节点的最短路径中的最大值int ans = *max_element(dist.begin() + 1, dist.end());// 如果最大值小于 INF,说明所有节点都可达,返回最大值作为网络延迟时间// 否则返回 -1,表示有节点无法到达return ans < INF ? ans : -1;}
};

时空复杂度

时间复杂度:O((V+E)logV)

空间复杂度:O(V+E)

其中V是节点数,E是边数。


华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务300+同学成功上岸!

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!

  • 60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

相关文章:

【Py/Java/C++三种语言详解】LeetCode743、网络延迟时间【单源最短路问题Djikstra算法】

可上 欧弟OJ系统 练习华子OD、大厂真题 绿色聊天软件戳 od1441了解算法冲刺训练&#xff08;备注【CSDN】否则不通过&#xff09; 文章目录 相关推荐阅读一、题目描述二、题目解析三、参考代码PythonJavaC 时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 相关推荐阅读 …...

交替输出

交替输出 题目&#xff1a;线程 1 输出 a 5 次&#xff0c;线程 2 输出 b 5 次&#xff0c;线程 3 输出 c 5 次。现在要求输出 abcabcabcabcabc wait notify 版 public class SyncWaitNotify {private volatile int flag;private volatile int loopNumber;public SyncWaitNo…...

JS(三)——更改html内数据

获取 DOM 元素&#xff0c;然后修改其属性或内容。使用 getElementById 方法获取特定 ID 的元素&#xff1a; <p id"myParagraph">这是初始的文本</p> const paragraph document.getElementById(myParagraph); paragraph.innerHTML 这是修改后的文本…...

CSS小玩意儿:文字适配背景

一&#xff0c;效果 二&#xff0c;代码 1&#xff0c;搭个框架 添加一张背景图片&#xff0c;在图片中显示一行文字。 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" conte…...

C++:平衡二叉搜索树之红黑树

一、红黑树的概念 红黑树&#xff0c; 和AVL都是二叉搜索树&#xff0c; 红黑树通过在每个节点上增加一个储存位表示节点的颜色&#xff0c; 可以是RED或者BLACK&#xff0c; 通过任何一条从根到叶子的路径上各个节点着色方式的限制&#xff0c;红黑树能够确保没有一条路径会比…...

CentOS 7 系统优化

CentOS 7 系统优化 1、配置YUM源 阿里云的YUM源配置&#xff1a; CentOS 7使用以下命令&#xff1a; sudo wget -O /etc/yum.repos.d/CentOS-Base.repo http://mirrors.aliyun.com/repo/Centos-7.repoCentOS 8使用以下命令&#xff1a; sudo wget -O /etc/yum.repos.d/CentOS…...

扫雷游戏——附源代码

扫雷游戏的源代码比较简单&#xff0c;不设计比较复杂的代码&#xff0c;主要是多个函数的组合&#xff0c;每个函数执行自己的功能&#xff0c;最终支持游戏的完成。 1.菜单 我们需要一个提醒信息来让用户进行选择。 void menu() {printf("***********************\n&…...

Vue3列表(List)

效果如下图&#xff1a;在线预览 APIs List 参数说明类型默认值bordered是否展示边框booleanfalsevertical是否使用竖直样式booleanfalsesplit是否展示分割线booleantruesize列表尺寸‘small’ | ‘middle’ | ‘large’‘middle’loading是否加载中booleanfalsehoverable是否…...

HarmonyOS NEXT - Navigation组件封装BaseNavigation

demo 地址: https://github.com/iotjin/JhHarmonyDemo 代码不定时更新&#xff0c;请前往github查看最新代码 在demo中这些组件和工具类都通过module实现了&#xff0c;具体可以参考HarmonyOS NEXT - 通过 module 模块化引用公共组件和utils 官方介绍 组件导航 (Navigation)(推…...

浅看MySQL数据库

有这么一句话&#xff1a;“一个不会数据库的程序员不是合格的程序员”。有点夸张&#xff0c;但是确是如此。透彻学习数据库是要学习好多知识&#xff0c;需要学的东西也是偏难的。我们今天来看数据库MySQL的一些简单基础东西&#xff0c;跟着小编一起来看一下吧。 什么是数据…...

Pytorch常用训练套路框架(CPU)

文章目录 1. 数据准备示例&#xff1a;加载 CIFAR-10 数据集 2. 模型定义示例&#xff1a;定义一个简单的卷积神经网络 3. 损失函数和优化器示例&#xff1a;定义损失函数和优化器 4. 训练循环示例&#xff1a;训练循环 5. 评估和测试示例&#xff1a;评估模型 6. 保存和加载模…...

C++ | Leetcode C++题解之第338题比特位计数

题目&#xff1a; 题解&#xff1a; class Solution { public:vector<int> countBits(int n) {vector<int> bits(n 1);for (int i 1; i < n; i) {bits[i] bits[i & (i - 1)] 1;}return bits;} };...

智慧校园云平台电子班牌系统源码,智慧教育一体化云解决方案

智慧校园云平台电子班牌系统&#xff0c;利用先进的云计算技术&#xff0c;将教育信息化资源和教学管理系统进行有效整合&#xff0c;实现生态基础数据共享、应用生态统一管理&#xff0c;为智慧教育建设的统一性&#xff0c;稳定性&#xff0c;可扩展性&#xff0c;互通性提供…...

数据库系统 第17节 数据仓库 案例赏析

下面我将通过几个具体的案例来说明数据仓库如何在不同的行业中发挥作用&#xff0c;并解决实际业务问题。 案例 1: 零售业 背景: 一家大型零售商希望改进其库存管理和市场营销策略&#xff0c;以提高销售额和顾客满意度。 解决方案: 数据仓库: 构建一个数据仓库&#xff0…...

硬件面试经典 100 题(71~90 题)

71、请问下图电路的作用是什么&#xff1f; 该电路实现 IIC 信号的电平转换&#xff08;3.3V 和 5V 电平转换&#xff09;&#xff0c;并且是双向通信的。 上下两路是一样的&#xff0c;只分析 SDA 一路&#xff1a; 1&#xff09; 从左到右通信&#xff08;SDA2 为输入状态&…...

【git】代理相关

问题&#xff1a; 开启了翻墙代理工具&#xff0c;拉取代码时报错&#xff1a;fatal: 无法访问 xxxx : Failed to connect to github.com port 443: 连接超时 解决&#xff1a; 0&#xff0c;取消代理仍然无法拉取 1&#xff0c;查看控制面板-网络与Internet-代理&#xff…...

golang gin框架中创建自定义中间件的2种方式总结 - func(*gin.Context)方式和闭包函数方式定义gin中间件

在gin框架中&#xff0c;我们可以通过2种方式创建自定义中间件&#xff1a; 1. 直接定义一个类型为 func(*gin.Context)的函数或者方法 这种方式是我们常用的方式&#xff0c;也就是定义一个参数为*gin.Context的函数或者方法。定义的方法就是创建一个 参数类型为 gin.Handler…...

Linux高级编程 8.13 文件IO

一、文件IO 操作系统为了方便用户使用系统功能而对外提供的一组系统函数。称之为 系统调用&#xff08;unistd.h&#xff09; 其中有个 文件IO&#xff0c;一般都是对设备文件操作,当然也可以对普通文件进行操作。 这是一个基于Linux内核的没有缓存的IO机制 文件IO特性&…...

【k8s】ubuntu18.04 containerd 手动从1.7.15 换为1.7.20

ubutnu18.04之前手动安装了1.7.15现在下载1.7.20containerd-1.7.20-linux-amd64.tar.gz root@k8s-worker-i58265u:/home/zhangbin# root@k8s-worker-i58265u:/home/zhangbin# https://github.com/containerd/containerd/releases/download/v1.7.20/containerd-1.7.20-linux-am…...

常用浮动方式

目录 一、标准流 二、float浮动 三、 flex浮动 3.1flex组成 3.2 主轴对齐方式 3.3侧轴对齐方式 3.4修改主轴方向 3.5弹性盒子换行 3.6行对齐方式 一、标准流 标签在网页中的默认排布规则 例如&#xff1a; 块元素独占一行、行内元素可以一行显示多个 二、float浮动 让块…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...