力扣labuladong一刷day49天迪杰斯特拉
力扣labuladong一刷day49天迪杰斯特拉
文章目录
- 力扣labuladong一刷day49天迪杰斯特拉
- 一、743. 网络延迟时间
- 二、1631. 最小体力消耗路径
- 三、1514. 概率最大的路径
一、743. 网络延迟时间
题目链接:https://leetcode.cn/problems/network-delay-time/
使用迪杰斯特拉解决加权图某点到所有节点距离的问题。
如果是无权图,采用广度优先遍历即可,就把图想象成一颗树,广度优先就可以说是层序遍历。
而加权图寻找最短距离,最经典算法就是迪杰斯特拉算法,我们可以计算出某一个点到任意一个之间的最短距离。我们采用优先级队列,里面的每一个元素记录的是某点到起点之间的最短距离,我们会一直按照最短距离更新,这样到达结尾后即可得到最短距离。
class Solution {public int networkDelayTime(int[][] times, int n, int k) {List<int[]>[] graph = new ArrayList[n + 1];for (int i = 0; i <= n; i++) {graph[i] = new ArrayList<>();}for (int[] time : times) {int a = time[0], b = time[1], c = time[2];graph[a].add(new int[]{b, c});}int[] dist = djk(k, graph);int res = -1;for (int i = 1; i < dist.length; i++) {if (dist[i] == Integer.MAX_VALUE) return -1;res = Math.max(res, dist[i]);}return res;}class State {int id;int sToMe;public State(int id, int sToMe) {this.id = id;this.sToMe = sToMe;}}int[] djk(int start, List<int[]>[] graph) {int[] dist = new int[graph.length];Arrays.fill(dist, Integer.MAX_VALUE);PriorityQueue<State> pq = new PriorityQueue<>((a, b) -> a.sToMe - b.sToMe);dist[start] = 0;pq.add(new State(start, 0));while (!pq.isEmpty()) {State poll = pq.poll();int id = poll.id;int cur = poll.sToMe;if (cur > dist[id]) continue;for (int[] ints : graph[id]) {int nextId = ints[0];int temp = dist[id] + ints[1];if (temp < dist[nextId]) {dist[nextId] = temp;pq.add(new State(nextId, temp));}}}return dist;}
}
二、1631. 最小体力消耗路径
题目链接:https://leetcode.cn/problems/path-with-minimum-effort/
思路:基本上就是迪杰斯特拉的典型题目,只不过这一次求的是最小消耗,但我们在过程中需要求每一条路径的最大消耗,在去往下一个点时选择这些最大消耗中的最小消耗,做为路径的延伸。
class Solution {public int minimumEffortPath(int[][] heights) {int r = heights.length, c = heights[0].length;return djk(heights);}List<int[]> getList(int x, int y, int r, int c) {int[][] temp = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};List<int[]> list = new ArrayList<>();for (int[] ints : temp) {int nx = x + ints[0], ny = y + ints[1];if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;list.add(new int[] {nx, ny});}return list;}class State {int x;int y;int sToMe;public State(int x, int y, int sToMe) {this.x = x;this.y = y;this.sToMe = sToMe;}}int djk(int[][] heights) {int r = heights.length, c = heights[0].length;int[][] dist = new int[r][c];PriorityQueue<State> pq = new PriorityQueue<>((a, b)-> a.sToMe - b.sToMe);for (int i = 0; i < r; i++) {Arrays.fill(dist[i], Integer.MAX_VALUE);}pq.add(new State(0, 0, 0));dist[0][0] = 0;while (!pq.isEmpty()) {State poll = pq.poll();int x = poll.x, y = poll.y;int cur = poll.sToMe;if (x == r-1 && y == c-1) return cur;if (cur > dist[x][y]) continue;for (int[] ints : getList(x, y, r, c)) {int nLen = Math.max(dist[x][y], Math.abs(heights[x][y]-heights[ints[0]][ints[1]]));if (nLen < dist[ints[0]][ints[1]]) {dist[ints[0]][ints[1]] = nLen;pq.add(new State(ints[0], ints[1], nLen));}}}return -1;}
}
三、1514. 概率最大的路径
题目链接:https://leetcode.cn/problems/path-with-maximum-probability/
思路:这题和上一题又有点不一样,相当于求最长路径,那么需要把优先级队列按照从大到小排序即可。
class Solution {public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {List<double[]>[] graph = new ArrayList[n];for (int i = 0; i < n; i++) {graph[i] = new ArrayList<>();}for (int i = 0; i < edges.length; i++) {int from = edges[i][0], to = edges[i][1];graph[from].add(new double[]{to, succProb[i]});graph[to].add(new double[]{from, succProb[i]});}return djk(graph, start_node, end_node);}class State{int id;double sToE;public State(int id, double sToE) {this.id = id;this.sToE = sToE;}}double djk(List<double[]>[] graph, int s, int e) {double[] dist = new double[graph.length];PriorityQueue<State> pq = new PriorityQueue<>((a, b)->Double.compare(b.sToE, a.sToE));Arrays.fill(dist, -1);dist[s] = 1;pq.add(new State(s, 1));while (!pq.isEmpty()) {State poll = pq.poll();int id = poll.id;double cur = poll.sToE;if (id == e) return cur;if (cur < dist[id]) continue;for (double[] ints : graph[id]) {int to = (int) ints[0];double nLen = cur * ints[1];if (nLen > dist[to]) {dist[to] = nLen;pq.add(new State(to, nLen));}}}return 0.0;}
}
相关文章:
力扣labuladong一刷day49天迪杰斯特拉
力扣labuladong一刷day49天迪杰斯特拉 文章目录 力扣labuladong一刷day49天迪杰斯特拉一、743. 网络延迟时间二、1631. 最小体力消耗路径三、1514. 概率最大的路径 一、743. 网络延迟时间 题目链接:https://leetcode.cn/problems/network-delay-time/ 使用迪杰斯特…...
MCS接口技术----定时/计数,中断
目录 一.中断系统相关寄存器 1.51单片机中断系统的总体结构: 2.中断源的中断级别(由高到低): 3.与中断有关的四个寄存器: (1)TCON---定时控制寄存器 (2)IE---中断允…...
Java开发框架和中间件面试题(10)
目录 104.怎么保证缓存和数据库数据的一致性? 105.什么是缓存穿透,什么是缓存雪崩?怎么解决? 106.如何对数据库进行优化? 107.使用索引时有哪些原则? 108.存储过程如何进行优化? 109.说说…...
C++ 具名要求-基本概念-指定该类型对象可以从右值构造
指定该类型对象可以从右值构造 指定该类型的实例可以从一个右值实参构造。 要求 以下情况下,类型 T 满足可移动构造 (MoveConstructible) : 给定 T 类型的右值表达式 rv任意标识符 u 下列表达式必须合法且拥有其指定的效果 表达式后条件T u rv;u…...
Python如何把类当做字典来访问及浅谈Python类命名空间
Python如何把类当做字典来访问 Python把类当做字典来访问 定义一个类将它实例化,我们可以通过obj.属性来访问类的属性,如果想获取类的所有实例变量,我们可以使用obj.__dict__来访问,如下: class A:def __init__(self)…...
简述Redis备份策略以及对应的实现机制
引言 Redis作为高性能的内存数据库,数据的安全性至关重要。一旦数据丢失,可能会对业务造成重大影响。因此,备份Redis数据是每个Redis使用者都必须考虑的问题。本文将介绍Redis的备份策略以及对应的实现机制。 一、备份策略 1.1 定期备份 …...
【5G PHY】5G 物理层加速卡介绍
博主未授权任何人或组织机构转载博主任何原创文章,感谢各位对原创的支持! 博主链接 本人就职于国际知名终端厂商,负责modem芯片研发。 在5G早期负责终端数据业务层、核心网相关的开发工作,目前牵头6G算力网络技术标准研究。 博客…...
lftp学习笔记
目录 0. ftp vs. lftp1. 安装2. 常用命令2.1 登录2.2 文件管理2.3 文件传输 3. 脚本编程4. 实践中的问题排查参考 0. ftp vs. lftp lftp是一款文件传输工具,支持FTP、HTTP、SFTP、FISH等多种协议。 功能ftplftp数据传输文件文件、文件夹多线程传输支持断点续传支持…...
idea 插件开发之 HelloWorld
前言 本文使用的 idea 2023.3 版本进行插件入门开发,首先要说明的是 idea 2023 版本及以后的 idea,对插件开发进行了一定程度的变动: 1、创建项目时不再支持 maven 选项 2、必须是 jdk17 及以后版本(点击查看官网版本对应关系&…...
极速文件搜索工具Everything结合内网穿透实现远程搜索本地文件
文章目录 前言1.软件安装完成后,打开Everything2.登录cpolar官网 设置空白数据隧道3.将空白数据隧道与本地Everything软件结合起来总结 前言 要搭建一个在线资料库,我们需要两个软件的支持,分别是cpolar(用于搭建内网穿透数据隧道…...
【PowerMockito:编写单元测试过程中采用when打桩失效的问题】
问题描述 正如上图所示,采用when打桩了,但是,实际执行的时候还是返回null。 解决方案 打桩时直接用any() 但是这样可能出现一个mybatisplus的异常,所以在测试类中需要加入以下代码片段: Beforepublic void setUp() …...
[蓝桥杯 2018省赛]回家路费
回家路费 题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 小明被不明势力劫持。后莫名其妙被扔到 X 星站再无问津。小明得知每天都有飞船飞往地球,但需要 108108 元的船票,而他却身无分文。…...
学生管理系统(vue + springboot)
学生管理系统(vuespringboot)资源-CSDN文库 项目介绍 这是一个采用前后端分离开发的项目,前端采用 Vue 开发、后端采用 Spring boot Mybatis 开发。 项目部署 ⭐️如果你有 docker 的话,直接 docker compose up 即可启动&#…...
算法(3)——二分查找
一、什么是二分查找 二分查找也称折半查找,是在一组有序(升序/降序)的数据中查找一个元素,它是一种效率较高的查找方法。 二、二分查找的原理 1、查找的目标数据元素必须是有序的。没有顺序的数据,二分法就失去意义。 2、数据元素通常是数值…...
golang实现可中断的流式下载
golang实现可中断的流式下载 最近有一个需要实现下载功能: 从服务器上读取文件,返回一个ReadCloser在用户磁盘上创建文件,通过io.Copy实现文件下载(io.Copy是流式的操作,不会出现因文件过大而内存暴涨的问题࿰…...
SpringBoot 医药咨询系统
概述 智慧医药系统(smart-medicine)是一个基于 SpringBoot 开发的Web 项目。整体页面简约大气,增加了AI医生问诊功能,功能设计的较为简单。 开源地址 https://gitcode.net/NVG_Haru/Java_04 界面预览 功能介绍 游客功能介绍 …...
C语言转WebAssembly的全流程,及Web端调用测试
第一步:安装环境 参考网址:https://emscripten.org/docs/getting_started/downloads.html 具体过程: 克隆代码:git clone https://github.com/emscripten-core/emsdk.git进入代码目录:cd emsdk获取最新远端代码&…...
前端--基础 目录文件夹和根目录 VScode打开目录文件夹
目录 目录文件夹和根目录 : 目录文件夹 : 根目录 : VScode 打开目录文件夹 : VScode 打开文件夹 : 拖拽目录文件夹 : 目录文件夹和根目录 : 我们都清楚,在实际的工作中会…...
传感器原理与应用复习--超声波、微波、红外及热电偶传感器
文章目录 上一篇超声波传感器微波传感器红外传感器热电偶传感器下一篇 上一篇 传感器原理与应用复习–光电式与半导体式传感器 超声波传感器 超过2万赫兹以上的波称为超声波 压电式超声波探头常用材料是压电晶体和压电陶瓷。它是利用压电材料的压电效应来工作的。 逆压电效…...
matlab概率论例子
高斯概率模型: [f,xi] ksdensity(x): returns a probability density estimate, f, for the sample in the vector x. The estimate is based on a normal kernel function, and is evaluated at 100 equally spaced points, xi, that cover the range of the da…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
手机平板能效生态设计指令EU 2023/1670标准解读
手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读,综合法规核心要求、最新修正及企业合规要点: 一、法规背景与目标 生效与强制时间 发布于2023年8月31日(OJ公报&…...
一些实用的chrome扩展0x01
简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序,无论是测试应用程序、搜寻漏洞还是收集情报,它们都能提升工作流程。 FoxyProxy 代理管理工具,此扩展简化了使用代理(如 Burp…...
用 FFmpeg 实现 RTMP 推流直播
RTMP(Real-Time Messaging Protocol) 是直播行业中常用的传输协议。 一般来说,直播服务商会给你: ✅ 一个 RTMP 推流地址(你推视频上去) ✅ 一个 HLS 或 FLV 拉流地址(观众观看用)…...
开疆智能Ethernet/IP转Modbus网关连接鸣志步进电机驱动器配置案例
在工业自动化控制系统中,常常会遇到不同品牌和通信协议的设备需要协同工作的情况。本案例中,客户现场采用了 罗克韦尔PLC,但需要控制的变频器仅支持 ModbusRTU 协议。为了实现PLC 对变频器的有效控制与监控,引入了开疆智能Etherne…...
第2课 SiC MOSFET与 Si IGBT 静态特性对比
2.1 输出特性对比 2.2 转移特性对比 2.1 输出特性对比 器件的输出特性描述了当温度和栅源电压(栅射电压)为某一具体数值时,漏极电流(集电极电流...
