【每日一题Day310】LC1654到家的最少跳跃次数 | BFS
到家的最少跳跃次数【LC1654】
有一只跳蚤的家在数轴上的位置
x
处。请你帮助它从位置0
出发,到达它的家。跳蚤跳跃的规则如下:
- 它可以 往前 跳恰好
a
个位置(即往右跳)。- 它可以 往后 跳恰好
b
个位置(即往左跳)。- 它不能 连续 往后跳
2
次。- 它不能跳到任何
forbidden
数组中的位置。跳蚤可以往前跳 超过 它的家的位置,但是它 不能跳到负整数 的位置。
给你一个整数数组
forbidden
,其中forbidden[i]
是跳蚤不能跳到的位置,同时给你整数a
,b
和x
,请你返回跳蚤到家的最少跳跃次数。如果没有恰好到达x
的可行方案,请你返回-1
。
-
思路:最短路问题,BFS
-
**BFS:**寻找最少跳跃次数,所以可以使用最短路径Dijkstra 算法,通过BFS实现,队列元素需要存储当前跳跃次数以及当前位置;
-
**记录状态:**由于跳跃时连续向前次数不受限制,但是不能连续向后跳两次,因此跳跃时还需要记录前一跳跃的状态为向后还是向前;
- 如果前一状态为向前,那么本次可以向前也可以向后
- 如果前一状态为向后,那么本次只可以向前
-
判断是否可以访问:
- 首先判断最远右边界,由于向前跳跃次数不受限制,避免超时,需要寻找最远右边界【重点】
- 当前位置不在
forbidden
数组中 - 之前没有访问过该状态【位置+方向】
-
寻找最远右边界:
-
如果 a ≥ b a\ge b a≥b,那么最远右边界为 x + b x+b x+b,在大于 x + b x+b x+b的位置不可能到达 x x x。
-
如果 a < b a\lt b a<b,那么可以先向前跳再向后跳逐步接近目标位置 x x x,最远右边界为 m a x ( f + a + b , x ) max(f+a+b, x) max(f+a+b,x),其中 f f f为 m a x ( f o r b i d d e n ) max(forbidden) max(forbidden)证明略。
感性认知:对于任何一条路径,若它包含了超过 m a x ( f + a + b , x ) max(f+a+b, x) max(f+a+b,x)的点,总能通过变换找到所有点都在 m a x ( f + a + b , x ) max(f+a+b, x) max(f+a+b,x)内的路径,且这条路径与原路径跳跃次数相同,对于该问题,这两条路径是等价的,所以只需考虑 m a x ( f + a + b , x ) max(f+a+b,x) max(f+a+b,x)内的路径即可
-
-
-
实现
class Solution {public int minimumJumps(int[] forbidden, int a, int b, int x) {Set<Integer> vis = new HashSet<>();Deque<int[]> pq = new LinkedList<>();// 跳跃次数、当前位置、连续向后跳次数int max = 0; for (int f : forbidden){vis.add(f);max = Math.max(max, f);} if (a > b){max = x + b;}else{max = Math.max(max + a + b, x);}boolean[][] flag = new boolean[max + 1][2];// 向前 向后一次flag[0][0] = true;pq.addLast(new int[]{0, 0, 0});while (!pq.isEmpty()){int[] node = pq.pollFirst();if (node[1] == x) return node[0]; // 向前int forward = node[1] + a;if (forward <= max && !vis.contains(forward) && !flag[forward][0]){flag[forward][0] = true;pq.addLast(new int[]{node[0] + 1, forward, 0});}// 向后int backward = node[1] - b;if (node[2] != 1 && backward >= 0 && !vis.contains(backward) && !flag[backward][1]){flag[backward][1] = true;pq.addLast(new int[]{node[0] + 1, backward, 1});}}return -1;} }
相关文章:
【每日一题Day310】LC1654到家的最少跳跃次数 | BFS
到家的最少跳跃次数【LC1654】 有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发,到达它的家。 跳蚤跳跃的规则如下: 它可以 往前 跳恰好 a 个位置(即往右跳)。它可以 往后 跳恰好 b 个位置(即往左跳&…...
[Android AIDL] --- AIDL原理简析
上一篇文章已经讲述了如何在Android studio中搭建基于aidl的cs模型框架,只是用起来了,这次对aidl及cs端如何调用的原理进行简单分析 1 创建AIDL文件 AIDL 文件可以分为两类。 一类是用来定义接口方法,声明要暴露哪些接口给客户端调用&#…...
企业的固定资产管理怎么操作
一家拥有多台大型设备的工厂,这些设备需要定期进行保养和维护,以确保其正常运转。而企业内部员工由于专业知识和技能的不同,需要分工协作才能更好地完成各项工作任务。因此,在设备资产管理方面,如何实现高效、便捷、透…...
Rust 进阶学习
Rust 进阶学习 文章目录 Rust 进阶学习所有权作用域移动和克隆涉及函数的所有权机制涉及参数的所有权涉及返回值的所有权 引用和租借可变引用 枚举类枚举成员的属性枚举匹配 结构体结构体方法结构体关联函数 错误处理不可恢复错误可恢复错误 Rust代码组织管理Module默认的Modul…...
保护网站安全:学习蓝莲花的安装和使用,复现跨站脚本攻击漏洞及XSS接收平台
这篇文章旨在用于网络安全学习,请勿进行任何非法行为,否则后果自负。 环境准备 一、XSS基础 1、反射型XSS 攻击介绍 原理 攻击者通过向目标网站提交包含恶意脚本的请求,然后将该恶意脚本注入到响应页面中,使其他用户在查看…...
Redis——如何解决redis穿透、雪崩、击穿问题
目录 一、查询商品信息的常规代码示例二、缓存击穿2.1、缓存击穿的理解2.2、缓存击穿的解决方案2.3、解决缓存击穿的代码示例 三、缓存雪崩3.1、缓存雪崩的理解3.2、缓存雪崩的解决方案3.2.1、缓存集中过期的情况3.2.2、缓存服务器宕机的情况3.2.3、缓存服务器断电的情况 3.3、…...
MySQL一行记录是如何存储的?
目录 MySQL的数据存放在哪个文件? 表空间文件的结构是怎么样的? 1、行(row) 2、页(page) 3、区(extent) 4、段(segment) InnoDB 行格式有哪些…...
[element-ui] el-tree全部展开与收回
shrinkTreeNode () {// 改变一个全局变量this.treeStatus !this.treeStatus;// 改变每个节点的状态this.changeTreeNodeStatus(this.$refs.attrList.store.root); },// 改变节点的状态 changeTreeNodeStatus (node) {node.expanded this.treeStatus;for (let i 0; i < no…...
git 统计(命令)
查询某人某个时刻提交了多少代码 added 添加代码 removed 删除代码 total 总代码 git log --author刘俊秦 --since2023-08-01 00:00:00 --until2023-08-23 23:00:00 --prettytformat: --numstat | awk { add $1; subs $2; loc $1 - $2 } END { printf "added lines: %s…...
斐波那契1(矩阵快速幂加速递推,斐波那契前n项平方和)
链接:登录—专业IT笔试面试备考平台_牛客网 来源:牛客网 Keven 特别喜欢斐波那契数列,已知 fib11fib_11fib11,fib21fib_21fib21,对于 n>3n>3n>3,fibnfibn−2fibn−1fib_{n}fib_{n-2}fib_{n…...
minikube mac 启动
系统信息如下 最开始使用的minikube是1.22.0版本,按照如下命令启动: minikube start --memory7851 --cpus4 --image-mirror-countrycn遇到了下面一些问题: 1、拉取coredns:v1.8.0镜像失败 Error response from daemon: manifest for regis…...
从零开始学习 Java:简单易懂的入门指南之查找算法及排序算法(二十)
查找算法及排序算法 常见的七种查找算法:1. 基本查找2. 二分查找3. 插值查找4. 斐波那契查找5. 分块查找6. 哈希查找7. 树表查找 四种排序算法:1. 冒泡排序1.1 算法步骤1.2 动图演示1.3 代码示例 2. 选择排序2.1 算法步骤2.2 动图演示 3. 插入排序3.1 算…...
非煤矿山风险监测预警算法 yolov8
非煤矿山风险监测预警算法通过yolov8网络模型深度学习算法框架,非煤矿山风险监测预警算法在煤矿关键地点安装摄像机等设备利用智能化视频识别技术,能够实时分析人员出入井口的情况,人数变化并检测作业状态。YOLO的结构非常简单,就…...
Ansible学习笔记(一)
1.什么是Ansible 官方网站:https://docs.ansible.com/ansible/latest/installation_guide/intro_installation.html Ansible是一个配置管理和配置工具,类似于Chef,Puppet或Salt。这是一款很简单也很容易入门的部署工具,它使用SS…...
2024毕业设计选题指南【附选题大全】
title: 毕业设计选题指南 - 如何选择合适的毕业设计题目 date: 2023-08-29 categories: 毕业设计 tags: 选题指南, 毕业设计, 毕业论文, 毕业项目 - 如何选择合适的毕业设计题目 当我们站在大学生活的十字路口,毕业设计便成了我们面临的一项重要使命。这不仅是对我们…...
Error: PostCSS plugin autoprefixer requires PostCSS 8 问题解决办法
报错:Error: PostCSS plugin autoprefixer requires PostCSS 8 原因:autoprefixer版本过高 解决方案: 降低autoprefixer版本 执行:npm i postcss-loader autoprefixer8.0.0...
pymongo通过oplog获取数据(mongodb)
使用 MongoDB 的 oplog(操作日志)进行数据同步是高级的用法,主要用于复制和故障恢复。需要确保源 MongoDB 实例是副本集的一部分,因为只有副本集才会维护 oplog。 以下是简化的步骤,描述如何使用 oplog 进行数据同步&…...
MySQL数据备份与恢复
备份的主要目的: 备份的主要目的是:灾难恢复,备份还可以测试应用、回滚数据修改、查询历史数据、审计等。 日志: MySQL 的日志默认保存位置为: /usr/local/mysql/data##配置文件 vim /etc/my.cnf [mysqld] ##错误日志…...
基于ssm+vue汽车售票网站源码和论文
基于ssmvue汽车售票网站源码和论文088 开发工具:idea 数据库mysql5.7 数据库链接工具:navcat,小海豚等 技术:ssm 摘 要 互联网发展至今,无论是其理论还是技术都已经成熟,而且它广泛参与在社会中的方方面面。它让…...
【List】List集合有序测试案例:ArrayList,LinkedList,Vector(123)
List是有序、可重复的容器。 有序: List中每个元素都有索引标记。可以根据元素的索引标记(在List中的位置)访问 元素,从而精确控制这些元素。 可重复: List允许加入重复的元素。更确切地讲,List通常允许满足 e1.equals(e2) 的元素…...
【javaweb】学习日记Day6 - Mysql 数据库 DDL DML
之前学习过的SQL语句笔记总结戳这里→【数据库原理与应用 - 第六章】T-SQL 在SQL Server的使用_Roye_ack的博客-CSDN博客 目录 一、概述 1、如何安装及配置路径Mysql? 2、SQL分类 二、DDL 数据定义 1、数据库操作 2、IDEA内置数据库使用 (1&…...
使用 PyTorch C ++前端
使用 PyTorch C 前端 PyTorch C 前端是 PyTorch 机器学习框架的纯 C 接口。 虽然 PyTorch 的主要接口自然是 Python,但此 Python API 建立于大量的 C 代码库之上,提供基本的数据结构和功能,例如张量和自动微分。 C 前端公开了纯 C 11 API&a…...
6、NoSQL的四大分类
6、NoSQL的四大分类 kv键值对 不同公司不同的实现 新浪:Redis美团:RedisTair阿里、百度:Redismemcache 文档型数据库(bson格式和json一样) MongoDB MongoDB是一个基于分布式文件存储的数据库,一般用于存储…...
(动态规划) 剑指 Offer 60. n个骰子的点数 ——【Leetcode每日一题】
❓ 剑指 Offer 60. n个骰子的点数 难度:中等 把 n 个骰子扔在地上,所有骰子朝上一面的点数之和为 s 。输入 n,打印出s的所有可能的值出现的概率。 你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点…...
ArrayList与顺序表
文章目录 一. 顺序表是什么二. ArrayList是什么三. ArrayList的构造方法四. ArrayList的常见方法4.1 add()4.2 size()4.3 remove()4.4 get()4.5 set()4.6 contains()4.7 lastIndexOf()和 indexOf()4.8 subList()4.9 clear() 以上就是ArrayList的常见方法!…...
【【萌新的STM32-22中断概念的简单补充】】
萌新的STM32学习22-中断概念的简单补充 我们需要注意的是这句话 从上面可以看出,STM32F1 供给 IO 口使用的中断线只有 16 个,但是 STM32F1 的 IO 口却远远不止 16 个,所以 STM32 把 GPIO 管脚 GPIOx.0~GPIOx.15(xA,B,C,D,E,F,G)分别对应中断…...
Java 中数据结构HashMap的用法
Java HashMap HashMap 是一个散列表,它存储的内容是键值对(key-value)映射。 HashMap 实现了 Map 接口,根据键的 HashCode 值存储数据,具有很快的访问速度,最多允许一条记录的键为 null,不支持线程同步。 HashMap 是…...
Request对象和response对象
一、概念 request对象和response对象是通过Servlet容器(如Tomcat)自动创建并传递给Servlet的。 Servlet容器负责接收客户端的请求,并将请求信息封装到request对象中,然后将request对象传 递给相应的Servlet进行处理。类似地&…...
设计模式之桥接模式
文章目录 一、介绍二、案例1. 组件抽象化2. 桥梁抽象化 一、介绍 桥接模式,属于结构型设计模式。通过提供抽象与实现之间的桥接结构,把抽象化与实现化解耦,使得二者可以独立变化。 《Head First 设计模式》: 将抽象和实现放在两…...
pom.xml配置文件失效,显示已忽略的pom.xml --- 解决方案
现象: 在 Maven 创建模块Moudle时,由于开始没有正确创建好,所以把它删掉了,然后接着又创建了与一个与之前被删除的Moudle同名的Moudle时,出现了 Ignore pom.xml,并且新创建的 Module 的 pom.xml配置文件失效…...
文本编辑器Vim常用操作和技巧
文章目录 1. Vim常用操作1.1 Vim简介1.2 Vim工作模式1.3 插入命令1.4 定位命令1.5 删除命令1.6 复制和剪切命令1.7 替换和取消命令1.8 搜索和搜索替换命令1.9 保存和退出命令 2. Vim使用技巧 1. Vim常用操作 1.1 Vim简介 Vim是一个功能强大的全屏幕文本编辑器,是L…...
【算法系列篇】位运算
文章目录 前言什么是位运算算法1.判断字符是否唯一1.1 题目要求1.2 做题思路1.3 Java代码实现 2. 丢失的数字2.1 题目要求2.2 做题思路2.3 Java代码实现 3. 两数之和3.1 题目要求3.2 做题思路3.3 Java代码实现 4. 只出现一次的数字4.1 题目要求4.2 做题思路4.3 Java代码实现 5.…...
机器学习的测试和验证(Machine Learning 研习之五)
关于 Machine Learning 研习之三、四,可到秋码记录上浏览。 测试和验证 了解模型对新案例的推广效果的唯一方法是在新案例上进行实际尝试。 一种方法是将模型投入生产并监控其性能。 这很有效,但如果你的模型非常糟糕,你的用户会抱怨——这…...
RNN循环神经网络
目录 一、卷积核与循环核 二、循环核 1.循环核引入 2.循环核:循环核按时间步展开。 3.循环计算层:向输出方向生长。 4.TF描述循环计算层 三、TF描述循环计算 四、RNN使用案例 1.数据集准备 2.Sequential中RNN 3.存储模型,acc和lose…...
安防视频监控/视频集中存储/云存储平台EasyCVR无法播放HLS协议该如何解决?
视频云存储/安防监控EasyCVR视频汇聚平台基于云边端智能协同,支持海量视频的轻量化接入与汇聚、转码与处理、全网智能分发、视频集中存储等。音视频流媒体视频平台EasyCVR拓展性强,视频能力丰富,具体可实现视频监控直播、视频轮播、视频录像、…...
Docker技术--Docker的安装
1..Docker的安装方式介绍 Docker官方提供了三种方式可以实现Docker环境的安装。分别为:Script、yum、rpm。在实际的环境中建议使用yum或者是rpm。 2..Docker的yum安装 # 1.下载docker wget https://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo -O /etc/yum.re…...
客户案例|MemFire Cloud助推应急管理业务,打造百万级数据可视化大屏
「导语」 硬石科技,成立于2018年,总部位于武汉,是一家专注于应急管理行业和物联感知预警算法模型的技术核心的物联网产品和解决方案提供商。硬石科技作为一家高新技术企业,持有6项发明专利,拥有100余项各类平台认证和资…...
蒲公英路由器如何设置远程打印?
现如今,打印机已经是企业日常办公中必不可少的设备,无论何时何地,总有需要用到打印的地方,包括资料文件、统计报表等等。 但若人在外地或分公司,有文件急需通过总部的打印机进行打印时,由于不在同一物理网络…...
国产自主可控C++工业软件可视化图形架构源码
关于国产自主代替的问题是当前热点,尤其是工业软件领域。 “一个功能强大的全自主C跨平台图形可视化架构对开发自主可控工业基础软件至关重要!” 作为全球领先的C工业基础图形可视化软件提供商,UCanCode软件有自己的思考,我们认…...
【linux命令讲解大全】022.网络管理工具和命令概述
文章目录 lsattr命令语法选项参数实例 nmcli补充说明语法选项OPTIONSOBJECT 实例 systemctl补充说明任务 旧指令 新指令 实例 开启防火墙22端口 从零学 python lsattr命令 用于查看文件的第二扩展文件系统属性。 语法 lsattr(选项)(参数) 选项 -E:可显示设备属…...
应急响应流程及思路
应急响应流程及思路 一:前言 对于还没有在项目中真正接触、参与过应急响应的同学来说,“应急响应”这四个字见的最多的就是建筑工地上的横幅 —— 人人懂应急,人人会响应。这里的应急响应和我们网络安全中的应急响应有着某种本质的相似&…...
网页自适应
自适应 那就要最好提前商量好 是全局自适应 或者是 局部自适应 一般网站页面纵向滚动条都是无法避免的 都是做横向适配也就是宽度 那就不能写死宽度像素 局部自适应 一般对父元素设置百分比就行 里面的子元素就设置固定像素、 比如一些登录 全局自适应 也就是要对每个元素…...
什么是Sui Kiosk,它可以做什么,如何赋能创作者?
创作者和IP持有者需要一些工具帮助他们在区块链上实现其商业模式。Sui Kiosk作为Sui上的一种原语可以满足这种需求,为创作者提供动态选项,使他们能够在任何交易场景中设置完成交易的条件。 本文将向您介绍为什么要在SuiFrens中使用Sui Kiosk,…...
【MySQL】mysql connect
目录 一、准备工作 1、创建mysql用户 2、删除用户 3、修改用户密码 3.1、自己改自己密码 3.2、root用户修改指定用户的密码 4、数据库的权限 4.1、给用户授权 4.2、回收权限 二、连接mysql client 1、安装mysql客户端库 2、验证是否引入成功 三、 mysql接口 1、初…...
基于 vue2 发布 npm包
背景:组件化开发需要,走了一遍发布npm包的过程,采用很简单的模式实现包的发布流程,记录如下。 项目参考:基于vue的时间播放器组件,并发布到npm_timeplay.js_xmy_wh的博客-CSDN博客 1、项目初始化 首先&a…...
基于Axios完成前后端分离项目数据交互
一、安装Axios npm i axios -S 封装一个请求工具:request.js import axios from axios// 创建可一个新的axios对象 const request axios.create({baseURL: http://localhost:9090, // 后端的接口地址 ip:porttimeout: 30000 })// request 拦截器 // 可以自请求…...
时序预测 | MATLAB实现基于PSO-BiLSTM、BiLSTM时间序列预测对比
时序预测 | MATLAB实现基于PSO-BiLSTM、BiLSTM时间序列预测对比 目录 时序预测 | MATLAB实现基于PSO-BiLSTM、BiLSTM时间序列预测对比效果一览基本描述程序设计参考资料 效果一览 基本描述 MATLAB实现基于PSO-BiLSTM、BiLSTM时间序列预测对比。 1.Matlab实现PSO-BiLSTM和BiLSTM…...
C# 生成唯一ID
1.首先通过nuget安装yitter.idgenerator 下面的三行代码搞定...
python怎么提取视频中的音频
目录 操作步骤 1. 安装MoviePy库: 2. 导入MoviePy库和所需的模块: 3. 提取音频: 可能遇到的问题 1. 编解码器支持: 2. 依赖项安装: 3. 文件路径问题: 4. 内存消耗: 5. 输出文件大小&a…...
学习设计模式之建造者模式,但是宝可梦
前言 作者在准备秋招中,学习设计模式,做点小笔记,用宝可梦为场景举例,有错误欢迎指出。 建造者模式 建造者模式是一种创建型模式,主要针对于某一个类有特别繁杂的属性,并且这些属性中有部分不是必须的。…...