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. 到家的最少跳跃次数 题目描述: 实现代码与解析: bfs 1654. 到家的最少跳跃次数 题目描述: 有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发,到达它的家。 跳蚤跳跃的规则如下: 它可以 …...
数据结构例题代码及其讲解-栈与队列
栈与队列 栈Stack 后进先出 栈的结构体定义及基本操作。 #define MaxSize 50 typedef struct {int data[MaxSize];//栈中存放数据类型为整型int top;//栈顶指针 }Stack;初始化 这里初始化时是将栈顶指针指向-1,有些则是指向0,因此后续入栈出栈…...
【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回归预测
🔆 文章首发于我的个人博客:欢迎大佬们来逛逛 数学建模:Logistic回归预测 Logistic回归预测 logistic方程的定义: x t 1 c a e b t x_{t}\frac{1}{cae^{bt}}\quad xtcaebt1 d x d t − a b e b t ( c a e b t ) 2 >…...

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

软件外包开发人员分类
在软件开发中,通常会分为前端开发和后端开发,下面和大家分享软件开发中的前端开发和后端开发分类和各自的职责,希望对大家有所帮助。北京木奇移动技术有限公司,专业的软件外包开发公司,欢迎交流合作。 1. 前端开发&…...
HTML 元素被定义为块级元素或内联元素
大多数 HTML 元素被定义为块级元素或内联元素。 10. 块级元素 块级元素在浏览器显示时,通常会以新行来开始(和结束)。 我们已经学习过的块级元素有: <h1>, <p>, <ul>, <table> 等。 值得注意的是: <p> 标签…...

单调递增的数字【贪心算法】
单调递增的数字 当且仅当每个相邻位数上的数字 x 和 y 满足 x < y 时,我们称这个整数是单调递增的。 给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增 。 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.如何查看有问题线程的具体信息,定位到代码的行数 使用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中,获取请…...

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

每日一题 1372二叉树中的最长交错路径
题目 给你一棵以 root 为根的二叉树,二叉树中的交错路径定义如下: 选择二叉树中 任意 节点和一个方向(左或者右)。如果前进方向为右,那么移动到当前节点的的右子节点,否则移动到它的左子节点。改变前进方…...

【力扣每日一题】2023.9.2 最多可以摧毁的敌人城堡数量
目录 题目: 示例: 分析: 代码: 题目: 示例: 分析: 这道题难在阅读理解,题目看得我匪夷所思,错了好多个测试用例才明白题目说的是什么。 我简单翻译一下就是寻找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逆向学习(一)vscode进行android逆向修改并重新打包 写在前面 其实我不知道这个文章能不能写下去,其实我已经开了很多坑但是都没填上,现在专利也发出去了,就开始填坑了,本坑的主要内容是关于androi…...

什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...

Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...

Axure 下拉框联动
实现选省、选完省之后选对应省份下的市区...
人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型
在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重,适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解,并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...
6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙
Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...
Vue 3 + WebSocket 实战:公司通知实时推送功能详解
📢 Vue 3 WebSocket 实战:公司通知实时推送功能详解 📌 收藏 点赞 关注,项目中要用到推送功能时就不怕找不到了! 实时通知是企业系统中常见的功能,比如:管理员发布通知后,所有用户…...