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

【每日一题Day310】LC1654到家的最少跳跃次数 | BFS

到家的最少跳跃次数【LC1654】

有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发,到达它的家。

跳蚤跳跃的规则如下:

  • 它可以 往前 跳恰好 a 个位置(即往右跳)。
  • 它可以 往后 跳恰好 b 个位置(即往左跳)。
  • 它不能 连续 往后跳 2 次。
  • 它不能跳到任何 forbidden 数组中的位置。

跳蚤可以往前跳 超过 它的家的位置,但是它 不能跳到负整数 的位置。

给你一个整数数组 forbidden ,其中 forbidden[i] 是跳蚤不能跳到的位置,同时给你整数 abx ,请你返回跳蚤到家的最少跳跃次数。如果没有恰好到达 x 的可行方案,请你返回 -1

  • 思路:最短路问题,BFS

    • **BFS:**寻找最少跳跃次数,所以可以使用最短路径Dijkstra 算法,通过BFS实现,队列元素需要存储当前跳跃次数以及当前位置;

    • **记录状态:**由于跳跃时连续向前次数不受限制,但是不能连续向后跳两次,因此跳跃时还需要记录前一跳跃的状态为向后还是向前;

      • 如果前一状态为向前,那么本次可以向前也可以向后
      • 如果前一状态为向后,那么本次只可以向前
    • 判断是否可以访问:

      • 首先判断最远右边界,由于向前跳跃次数不受限制,避免超时,需要寻找最远右边界【重点】
      • 当前位置不在forbidden数组中
      • 之前没有访问过该状态【位置+方向】
    • 寻找最远右边界:

      • 如果 a ≥ b a\ge b ab,那么最远右边界为 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 出发&#xff0c;到达它的家。 跳蚤跳跃的规则如下&#xff1a; 它可以 往前 跳恰好 a 个位置&#xff08;即往右跳&#xff09;。它可以 往后 跳恰好 b 个位置&#xff08;即往左跳&…...

[Android AIDL] --- AIDL原理简析

上一篇文章已经讲述了如何在Android studio中搭建基于aidl的cs模型框架&#xff0c;只是用起来了&#xff0c;这次对aidl及cs端如何调用的原理进行简单分析 1 创建AIDL文件 AIDL 文件可以分为两类。 一类是用来定义接口方法&#xff0c;声明要暴露哪些接口给客户端调用&#…...

企业的固定资产管理怎么操作

一家拥有多台大型设备的工厂&#xff0c;这些设备需要定期进行保养和维护&#xff0c;以确保其正常运转。而企业内部员工由于专业知识和技能的不同&#xff0c;需要分工协作才能更好地完成各项工作任务。因此&#xff0c;在设备资产管理方面&#xff0c;如何实现高效、便捷、透…...

Rust 进阶学习

Rust 进阶学习 文章目录 Rust 进阶学习所有权作用域移动和克隆涉及函数的所有权机制涉及参数的所有权涉及返回值的所有权 引用和租借可变引用 枚举类枚举成员的属性枚举匹配 结构体结构体方法结构体关联函数 错误处理不可恢复错误可恢复错误 Rust代码组织管理Module默认的Modul…...

保护网站安全:学习蓝莲花的安装和使用,复现跨站脚本攻击漏洞及XSS接收平台

这篇文章旨在用于网络安全学习&#xff0c;请勿进行任何非法行为&#xff0c;否则后果自负。 环境准备 一、XSS基础 1、反射型XSS 攻击介绍 原理 攻击者通过向目标网站提交包含恶意脚本的请求&#xff0c;然后将该恶意脚本注入到响应页面中&#xff0c;使其他用户在查看…...

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的数据存放在哪个文件&#xff1f; 表空间文件的结构是怎么样的&#xff1f; 1、行&#xff08;row&#xff09; 2、页&#xff08;page&#xff09; 3、区&#xff08;extent&#xff09; 4、段&#xff08;segment&#xff09; InnoDB 行格式有哪些&#xf…...

[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项平方和)

链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源&#xff1a;牛客网 Keven 特别喜欢斐波那契数列&#xff0c;已知 fib11fib_11fib1​1&#xff0c;fib21fib_21fib2​1&#xff0c;对于 n>3n>3n>3&#xff0c;fibnfibn−2fibn−1fib_{n}fib_{n-2}fib_{n…...

minikube mac 启动

系统信息如下 最开始使用的minikube是1.22.0版本&#xff0c;按照如下命令启动&#xff1a; minikube start --memory7851 --cpus4 --image-mirror-countrycn遇到了下面一些问题&#xff1a; 1、拉取coredns:v1.8.0镜像失败 Error response from daemon: manifest for regis…...

从零开始学习 Java:简单易懂的入门指南之查找算法及排序算法(二十)

查找算法及排序算法 常见的七种查找算法&#xff1a;1. 基本查找2. 二分查找3. 插值查找4. 斐波那契查找5. 分块查找6. 哈希查找7. 树表查找 四种排序算法&#xff1a;1. 冒泡排序1.1 算法步骤1.2 动图演示1.3 代码示例 2. 选择排序2.1 算法步骤2.2 动图演示 3. 插入排序3.1 算…...

非煤矿山风险监测预警算法 yolov8

非煤矿山风险监测预警算法通过yolov8网络模型深度学习算法框架&#xff0c;非煤矿山风险监测预警算法在煤矿关键地点安装摄像机等设备利用智能化视频识别技术&#xff0c;能够实时分析人员出入井口的情况&#xff0c;人数变化并检测作业状态。YOLO的结构非常简单&#xff0c;就…...

Ansible学习笔记(一)

1.什么是Ansible 官方网站&#xff1a;https://docs.ansible.com/ansible/latest/installation_guide/intro_installation.html Ansible是一个配置管理和配置工具&#xff0c;类似于Chef&#xff0c;Puppet或Salt。这是一款很简单也很容易入门的部署工具&#xff0c;它使用SS…...

2024毕业设计选题指南【附选题大全】

title: 毕业设计选题指南 - 如何选择合适的毕业设计题目 date: 2023-08-29 categories: 毕业设计 tags: 选题指南, 毕业设计, 毕业论文, 毕业项目 - 如何选择合适的毕业设计题目 当我们站在大学生活的十字路口&#xff0c;毕业设计便成了我们面临的一项重要使命。这不仅是对我们…...

Error: PostCSS plugin autoprefixer requires PostCSS 8 问题解决办法

报错&#xff1a;Error: PostCSS plugin autoprefixer requires PostCSS 8 原因&#xff1a;autoprefixer版本过高 解决方案&#xff1a; 降低autoprefixer版本 执行&#xff1a;npm i postcss-loader autoprefixer8.0.0...

pymongo通过oplog获取数据(mongodb)

使用 MongoDB 的 oplog&#xff08;操作日志&#xff09;进行数据同步是高级的用法&#xff0c;主要用于复制和故障恢复。需要确保源 MongoDB 实例是副本集的一部分&#xff0c;因为只有副本集才会维护 oplog。 以下是简化的步骤&#xff0c;描述如何使用 oplog 进行数据同步&…...

MySQL数据备份与恢复

备份的主要目的&#xff1a; 备份的主要目的是&#xff1a;灾难恢复&#xff0c;备份还可以测试应用、回滚数据修改、查询历史数据、审计等。 日志&#xff1a; MySQL 的日志默认保存位置为&#xff1a; /usr/local/mysql/data##配置文件 vim /etc/my.cnf [mysqld] ##错误日志…...

基于ssm+vue汽车售票网站源码和论文

基于ssmvue汽车售票网站源码和论文088 开发工具&#xff1a;idea 数据库mysql5.7 数据库链接工具&#xff1a;navcat,小海豚等 技术&#xff1a;ssm 摘 要 互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xff0c;而且它广泛参与在社会中的方方面面。它让…...

【List】List集合有序测试案例:ArrayList,LinkedList,Vector(123)

List是有序、可重复的容器。 有序&#xff1a; List中每个元素都有索引标记。可以根据元素的索引标记(在List中的位置)访问 元素&#xff0c;从而精确控制这些元素。 可重复&#xff1a; List允许加入重复的元素。更确切地讲&#xff0c;List通常允许满足 e1.equals(e2) 的元素…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...

数据结构:递归的种类(Types of Recursion)

目录 尾递归&#xff08;Tail Recursion&#xff09; 什么是 Loop&#xff08;循环&#xff09;&#xff1f; 复杂度分析 头递归&#xff08;Head Recursion&#xff09; 树形递归&#xff08;Tree Recursion&#xff09; 线性递归&#xff08;Linear Recursion&#xff09;…...