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

LeetCode每日一题:1654. 到家的最少跳跃次数(2023.8.30 C++)

目录

1654. 到家的最少跳跃次数

题目描述:

实现代码与解析:

bfs


1654. 到家的最少跳跃次数

题目描述:

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

跳蚤跳跃的规则如下:

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

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

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

示例 1:

输入:forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
输出:3
解释:往前跳 3 次(0 -> 3 -> 6 -> 9),跳蚤就到家了。

示例 2:

输入:forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
输出:-1

示例 3:

输入:forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
输出:2
解释:往前跳一次(0 -> 16),然后往回跳一次(16 -> 7),跳蚤就到家了。

提示:

  • 1 <= forbidden.length <= 1000
  • 1 <= a, b, forbidden[i] <= 2000
  • 0 <= x <= 2000
  • forbidden 中所有位置互不相同。
  • 位置 x 不在 forbidden 中。

实现代码与解析:

bfs

class Solution {
public:int minimumJumps(vector<int>& forbidden, int a, int b, int x) {unordered_set<int> f; // 记录禁止的位置,和前进访问过的位置,防止死循环for (auto &t: forbidden) f.insert(t); queue<tuple<int, int, bool>> q; // 当前位置,当前步数,到此位置是前进还是后退而来 true 前进 false 后退q.push({0, 0, false}); // 初始化,起点 不能后退为负数,当作false处理// bfswhile (q.size()){auto [j, k, l] = q.front();q.pop(); // 出队if (j == x) return k; // 到家的位置,返回步数// 向前,位置合法 且 不超过范围if (!f.count(j + a) && j + a <= 6000) {q.push({j + a, k + 1, true}); //入队f.insert(j + a); // 标记位置}// 向后,位置合法 且 不超过范围,并且不能连续两次向后if (l && !f.count(j - b) && j - b >= 0){q.push({j - b, k + 1, false}); //入队}}return -1;}
};

原理思路:

        一开始很容易觉得是dp来写,其实是bfs,dfs只能求一个符合条件的结果,而bfs是求最短。

        其实注释写的已经很清楚了,可以直接看注释。

        队列记录:当前位置,当前步数,到此位置是前进还是后退而来。

        bfs首先写得到结果的条件,就是到家了 j == x。

        前进时,判断要到的位置是否合法,且不超过上界,上界可以看力扣官解的证明,太麻烦了,试一个相对较大符合条件的数就行。入队并且标记位置,后退时不能到已经走过的位置,因为只能退一次,要是到已经走过的位置,只能往前,不就重复了么。

        后退时,判断大于等于0,并且位置合法即可。

        若没有符合条件的结果,返回 -1。

感觉以后可以改用emplace,很多人都这样写,代替push和insert确实方便,而且还快。

相关文章:

LeetCode每日一题:1654. 到家的最少跳跃次数(2023.8.30 C++)

目录 1654. 到家的最少跳跃次数 题目描述&#xff1a; 实现代码与解析&#xff1a; bfs 1654. 到家的最少跳跃次数 题目描述&#xff1a; 有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发&#xff0c;到达它的家。 跳蚤跳跃的规则如下&#xff1a; 它可以 …...

数据结构例题代码及其讲解-栈与队列

栈与队列 栈Stack 后进先出 ​ 栈的结构体定义及基本操作。 #define MaxSize 50 typedef struct {int data[MaxSize];//栈中存放数据类型为整型int top;//栈顶指针 }Stack;初始化 ​ 这里初始化时是将栈顶指针指向-1&#xff0c;有些则是指向0&#xff0c;因此后续入栈出栈…...

【Spark】Pyspark RDD

1. RDD算子1.1 文件 <> rdd对象1.2 map、foreach、mapPartitions、foreach Partitions1.3 flatMap 先map再解除嵌套1.4 reduceByKey、reduce、fold 分组聚合1.5 mapValue 二元组value进行map操作1.6 groupBy、groupByKey1.7 filter、distinct 过滤筛选1.8 union 合并1.9 …...

数学建模:Logistic回归预测

&#x1f506; 文章首发于我的个人博客&#xff1a;欢迎大佬们来逛逛 数学建模&#xff1a;Logistic回归预测 Logistic回归预测 logistic方程的定义&#xff1a; x t 1 c a e b t x_{t}\frac{1}{cae^{bt}}\quad xt​caebt1​ d x d t − a b e b t ( c a e b t ) 2 >…...

一个面向MCU的小型前后台系统

JxOS简介 JxOS面向MCU的小型前后台系统&#xff0c;提供消息、事件等服务&#xff0c;以及软件定时器&#xff0c;低功耗管理&#xff0c;按键&#xff0c;led等常用功能模块。 gitee仓库地址为&#xff08;复制到浏览器打开&#xff09;&#xff1a; https://gitee.com/jer…...

软件外包开发人员分类

在软件开发中&#xff0c;通常会分为前端开发和后端开发&#xff0c;下面和大家分享软件开发中的前端开发和后端开发分类和各自的职责&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎交流合作。 1. 前端开发&…...

HTML 元素被定义为块级元素或内联元素

大多数 HTML 元素被定义为块级元素或内联元素。 10. 块级元素 块级元素在浏览器显示时&#xff0c;通常会以新行来开始&#xff08;和结束&#xff09;。 我们已经学习过的块级元素有: <h1>, <p>, <ul>, <table> 等。 值得注意的是: <p> 标签…...

单调递增的数字【贪心算法】

单调递增的数字 当且仅当每个相邻位数上的数字 x 和 y 满足 x < y 时&#xff0c;我们称这个整数是单调递增的。 给定一个整数 n &#xff0c;返回 小于或等于 n 的最大数字&#xff0c;且数字呈 单调递增 。 public class Solution {public int monotoneIncreasingDigits…...

gnuradio-hackrf_info.exe -FM频率使用

97910000...

JVM学习(三)--生产环境的线程问题诊断

1.如何定位哪个进程对cpu占用过高 使用top命令 2.如何定位到某个进程的具体某个线程 使用ps H -eo pid,tid,%cpu | grep 进程id (可以具体定位到某个进程的某个线程的cpu占用情况) 3.如何查看有问题线程的具体信息&#xff0c;定位到代码的行数 使用jstack 进程id 可以找…...

PHP数组处理$arr1转换为$arr2

请编写一段程序将$arr1转换为$arr2 $arr1 array( 0>array (fid>1,tid>1,name>Name1), 1>array (fid>2,tid>2,name>Name2), 2>array (fid>3,tid>5,name>Name3), 3>array (fid>4,tid>7,name>Name4), 4>array (fid>5,tid…...

ATF(TF-A)安全通告 TFV-10 (CVE-2022-47630)

安全之安全(security)博客目录导读 ATF(TF-A)安全通告汇总 目录 一、ATF(TF-A)安全通告 TFV-10 (CVE-2022-47630) 二、CVE-2022-47630 2.1 Bug 1:证书校验不足 2.2 Bug 2:auth_nvctr()中缺少边界检查...

详解 SpringMVC 中获取请求参数

文章目录 1、通过ServletAPI获取2、通过控制器方法的形参获取请求参数3、[RequestParam ](/RequestParam )4、[RequestHeader ](/RequestHeader )5、[CookieValue ](/CookieValue )6、通过POJO获取请求参数7、解决获取请求参数的乱码问题总结 在Spring MVC中&#xff0c;获取请…...

Message: ‘chromedriver‘ executable may have wrong permissions.

今天运行项目遇到如下代码 driverwebdriver.Chrome(chrome_driver, chrome_optionsoptions)上述代码运行报错如下&#xff1a; Message: chromedriver executable may have wrong permissions. Please see https://sites.google.com/a/chromium.org/chromedriver/home出错的原…...

每日一题 1372二叉树中的最长交错路径

题目 给你一棵以 root 为根的二叉树&#xff0c;二叉树中的交错路径定义如下&#xff1a; 选择二叉树中 任意 节点和一个方向&#xff08;左或者右&#xff09;。如果前进方向为右&#xff0c;那么移动到当前节点的的右子节点&#xff0c;否则移动到它的左子节点。改变前进方…...

【力扣每日一题】2023.9.2 最多可以摧毁的敌人城堡数量

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 这道题难在阅读理解&#xff0c;题目看得我匪夷所思&#xff0c;错了好多个测试用例才明白题目说的是什么。 我简单翻译一下就是寻找1和…...

kotlin实现java的单例模式

代码 package com.flannery.interviewdemo.singleinstance//https://blog.csdn.net/Jason_Lee155/article/details/128796742 Java实现 //public class SingletonDemo { // private static SingletonDemo instancenew SingletonDemo(); // private SingletonDemo() // …...

使用 KeyValueDiffers 检测Angular 对象的变化

使用 KeyValueDiffers 检测Angular 对象的变化 ngDoCheck钩子 ngDoCheck 是 Angular 生命周期钩子之一。它允许组件在 Angular 检测到变化时执行自定义的变化检测逻辑。 当任何组件或指令的输入属性发生变化、在组件内部发生了变更检测周期或者当主动触发变更检测策略&#…...

Macos 10.13.2安装eclipse

eclipse for php 安装2021-12最后版本4.22 2021-12 R | Eclipse Packages jdk17 x64 dmg安装包,要安装jdk这个才能运行 Java Downloads | Oracle...

Android逆向学习(一)vscode进行android逆向修改并重新打包

Android逆向学习&#xff08;一&#xff09;vscode进行android逆向修改并重新打包 写在前面 其实我不知道这个文章能不能写下去&#xff0c;其实我已经开了很多坑但是都没填上&#xff0c;现在专利也发出去了&#xff0c;就开始填坑了&#xff0c;本坑的主要内容是关于androi…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...