leetcode 1631.最小体力消耗路径
思路:BFS+二分
这道题和洛谷上的那个“汽车拉力赛”那道题很相似,但是这道题相较于洛谷那个来说会简单一些。
这里作者一开始写的时候思路堵在了怎么在BFS中用二分,先入为主的以为需要先写出来搜索函数然后再去处理二分的事,但是这里是先二分找数,然后再搜索才是对的。所以先入为主之后就没有做出来。
注意:需要注意数据范围,另外,每一次更新mid数值的时候,我们上一次已经搜索过的数组,队列等存储单元都需要清空,不然的话会影响后面的输出结果。还有,二分注意用哪一个模板,选择也是很重要的。这里主要是求最小值,所以是(left+right)/2而不是(left+right+1)/2,还有就是while中不要left<=right,你用范围的二分查找会造成死循环,但是用于基本的找数是可以的。
class Solution {
public:int minimumEffortPath(vector<vector<int>>& heights) {int dx[4]={1,-1,0,0};int dy[4]={0,0,1,-1};int left=0;int right=1000000;while(left<right){queue<pair<int,int>>q;q.push({0,0});vector<vector<bool>>st(heights.size(),vector<bool>(heights[0].size(),false));st[0][0]=true;int mid=(left+right)/2;while(!q.empty()){auto tmp=q.front();q.pop();for(int i=0;i<4;i++){int a=dx[i]+tmp.first;int b=dy[i]+tmp.second;if(a>=heights.size()||a<0||b<0||b>=heights[0].size())continue;if(st[a][b])continue;if(abs(heights[a][b]-heights[tmp.first][tmp.second])>mid)continue;q.push({a,b});st[a][b]=true;}}if(st[heights.size()-1][heights[0].size()-1]){right=mid;}else{left=mid+1;}}return right;}
};
相关文章:
leetcode 1631.最小体力消耗路径
思路:BFS二分 这道题和洛谷上的那个“汽车拉力赛”那道题很相似,但是这道题相较于洛谷那个来说会简单一些。 这里作者一开始写的时候思路堵在了怎么在BFS中用二分,先入为主的以为需要先写出来搜索函数然后再去处理二分的事,但是…...
【ARM64 常见汇编指令学习 19.2 -- ARM64 地址加载指令 ADR 详细介绍】
文章目录 地址加载指令 ADRADR 指令使用场景例子注意事项 地址加载指令 ADR ARMv8 架构引入了一系列的改进和扩展,包括对汇编指令集的更新。在这之中,ADR 指令是一个重要的组成部分,它用于计算并加载一个地址到寄存器。 ADR 指令 ADR 指令…...
vscode输出控制台中文显示乱码最有效解决办法
当VSCode的输出控制台中文显示乱码时,一个有效的解决办法是通过设置环境变量来确保编码的正确性。以下是解决方式: 首先,设置环境变量以修正乱码问题: 如果上述方法没有解决乱码问题,请继续以下步骤: 右键…...
springboot + Vue前后端项目(第十五记)
项目实战第十五记 写在前面1.后端接口实现1.1 用户表添加角色字段1.2 角色表增加唯一标识字段1.3 UserDTO1.4 UserServiceImpl1.5 MenuServiceImpl 2. 前端实现2.1 User.vue2.2 动态菜单设计2.2.1 Login.vue2.2.2 Aside.vue 2.3 动态路由设计2.3.1 菜单表新增字段page_path2.3.…...
如何在Windows 11中恢复丢失的快速访问菜单?这里提供解决办法
序言 在电脑的“快速访问”菜单中找不到固定的项目?或者,整个菜单对你来说已经消失了吗?无论哪种方式,你都可以强制你的电脑恢复菜单并显示其中的所有项目。以下是如何在你的Windows 11电脑上做到这一点。 将文件资源管理器设置为打开到主页 当你在文件资源管理器的左侧…...
变声器软件免费版有哪些?国内外12大热门变声器大盘点!(新)
变声软件是一种人工智能AI音频处理工具,允许用户实时修改自己的声音或改变预先录制的音频。这些软件解决方案可提供不同的效果,如改变声音的音调或速度,或将我们的声音转换成其他人或其他东西的声音,如名人、卡通人物、机器人或不…...
计算机网络 —— 数据链路层(无线局域网)
计算机网络 —— 数据链路层(无线局域网) 什么是无线局域网IEEE 802.11主要标准及其特点: 802.11的MAC帧样式 我们来看看无线局域网: 什么是无线局域网 无线局域网(Wireless Local Area Network,简称WLAN…...
SpringBoot图书管理系统【附:资料➕文档】
前言:我是源码分享交流Coding,专注JavaVue领域,专业提供程序设计开发、源码分享、 技术指导讲解、各类项目免费分享,定制和毕业设计服务! 免费获取方式--->>文章末尾处! 项目介绍048: 图…...
shell简介
一、Shell 概念定义 Shell 是用 C 语言编写的程序,是用户使用 Linux 的桥梁,既是命令语言又是程序设计语言。 shell 脚本为 Shell 编写的脚本程序,常说的 shell 通常指 shell 脚本。 包含一系列命令的文本文件,这些命令按照特定…...
使用 Scapy 库编写 ICMP 不可达攻击脚本
一、介绍 ICMP不可达攻击是一种利用ICMP(Internet Control Message Protocol)不可达消息来干扰或中断目标系统的网络通信的攻击类型。通过发送伪造的ICMP不可达消息,攻击者可以诱使目标系统认为某些网络路径或主机不可达,从而导致…...
Electron qt开发教程
模块安装打包 npm install -g electron-forge electron-forge init my-project --templatevue npm start //进入目录启动 //打包成一个目录到out目录下,注意这种打包一般用于调试,并不是用于分发 npm run package //打出真正的分发包,放在o…...
尝试用 GPT-4o 写 2024高考语文作文
文章目录 新课标I卷科技进步与问题的演变 新课标II卷抵达未知之境:探索与成长的旅程 全国甲卷坦诚交流:构建真正相遇的桥梁 北京卷历久弥新 天津卷定义与自定义:在世界的缤纷中前行 上海卷认可度的思考与反思 新课标I卷 阅读下面的材料&#…...
自动化Reddit图片收集:Python爬虫技巧
引言 Reddit,作为一个全球性的社交平台,拥有海量的用户生成内容,其中包括大量的图片资源。对于数据科学家、市场研究人员或任何需要大量图片资源的人来说,自动化地从Reddit收集图片是一个极具价值的技能。本文将详细介绍如何使用…...
自动驾驶人工智能
自动驾驶技术中使用的算法和滤波器 如何部署软件中的算法和滤波器,以增强传感器数据的可用性和应用性 自动驾驶人工智能 文章目录 一、介绍二、自动驾驶的算法2.1 感知算法2.2 本地化算法2.3 映射算法2.4 规划算法2.5 控制算法2.6 过滤 器2.7 卡尔曼滤波器2.8 颗粒过…...
基础乐理入门
基础概念 乐音:音高(频率)固定,振动规则的音。钢琴等乐器发出的是乐音,听起来悦耳、柔和。噪音:振动不规则,音高也不明显的音。风声、雨声、机器轰鸣声是噪音,大多数打击乐器&#…...
mysql 8 linux7,8安装教程
选择自己对应的linux版本 cat /etc/os-release //查看自己linux系统版本 1.mysql下载地址 MySQL :: Download MySQL Community Server (Archived Versions) 拉到下面找到 选择自己linux指定的版本,否则会很麻烦 cat /etc/os-release //查看系统版本 2.查…...
『矩阵论笔记』特征分解(eigendecomposition)通俗解释!
特征分解(eigendecomposition)通俗解释! 文章目录 一. 特征分解(eigendecomposition)通俗解释!1. 它是如何工作的2. 试图达到什么目的3. 为什么它有用(将一个方阵分解成这三个组成矩阵有什么好处呢?)二. 参考文献一. 特征分解(eigendecomposition)通俗解释! 大家好,欢迎回…...
顶级域名和二级域名的区别
互联网是一个由无数个网络节点组成的复杂系统,而域名则是这个系统中用于识别和定位这些节点的重要工具。在域名体系中,顶级域名(Top-Level Domain,TLD)和二级域名(Second-Level Domain,SLD)是两个基本的层级概念。本文将探讨这两者…...
深入解析Kafka消息丢失的原因与解决方案
深入解析Kafka消息丢失的原因与解决方案 Apache Kafka是一种高吞吐量、分布式的消息系统,广泛应用于实时数据流处理。然而,在某些情况下,Kafka可能会出现消息丢失的情况,这对于数据敏感的应用来说是不可接受的。本文将深入解析Ka…...
【Python列表解锁】:掌握序列精髓,驾驭动态数据集合
文章目录 🚀一、列表🌈二、常规操作💥增💥删💥改💥查 ⭐三、补充操作 🚀一、列表 列表是一个能够存储多个同一或不同元素的序列 列表:list ---- [] 列表属于序列类型(容器…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
CSS3相关知识点
CSS3相关知识点 CSS3私有前缀私有前缀私有前缀存在的意义常见浏览器的私有前缀 CSS3基本语法CSS3 新增长度单位CSS3 新增颜色设置方式CSS3 新增选择器CSS3 新增盒模型相关属性box-sizing 怪异盒模型resize调整盒子大小box-shadow 盒子阴影opacity 不透明度 CSS3 新增背景属性ba…...
算法刷题-回溯
今天给大家分享的还是一道关于dfs回溯的问题,对于这类问题大家还是要多刷和总结,总体难度还是偏大。 对于回溯问题有几个关键点: 1.首先对于这类回溯可以节点可以随机选择的问题,要做mian函数中循环调用dfs(i&#x…...
在Spring Boot中集成RabbitMQ的完整指南
前言 在现代微服务架构中,消息队列(Message Queue)是实现异步通信、解耦系统组件的重要工具。RabbitMQ 是一个流行的消息中间件,支持多种消息协议,具有高可靠性和可扩展性。 本博客将详细介绍如何在 Spring Boot 项目…...
C/Python/Go示例 | Socket Programing与RPC
Socket Programming介绍 Computer networking这个领域围绕着两台电脑或者同一台电脑内的不同进程之间的数据传输和信息交流,会涉及到许多有意思的话题,诸如怎么确保对方能收到信息,怎么应对数据丢失、被污染或者顺序混乱,怎么提高…...
【Java基础】向上转型(Upcasting)和向下转型(Downcasting)
在面向对象编程中,转型(Casting) 是指改变对象的引用类型,主要涉及 继承关系 和 多态。 向上转型(Upcasting) ⬆️ 定义 将 子类对象 赋值给 父类引用(自动完成,无需强制转换&…...
