当前位置:网站首页>LeetCode 1654. 到家的最少跳跃次数 每日一题
LeetCode 1654. 到家的最少跳跃次数 每日一题
2022-07-07 15:32:00 【@小红花】
问题描述
有一只跳蚤的家在数轴上的位置 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 中。来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/minimum-jumps-to-reach-home
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
Java
class Solution {
public int minimumJumps(int[] forbidden, int a, int b, int x) {
//记录禁止到达的位置
Set<Integer> set = new HashSet<>();
for(int forbid : forbidden) set.add(forbid);
Queue<int[]> queue = new LinkedList<>();//当前位置,往回跳的次数
queue.offer(new int[]{0,0});
boolean[][] visible = new boolean[8000][2];
int ans = -1;
while(!queue.isEmpty()){
int size = queue.size();
ans++;
for(int i = 0;i < size;i++){
int[] t = queue.poll();
int position = t[0];
if(position == x) return ans;
int rollbackCount = t[1];
if(visible[position][rollbackCount]) continue;
visible[position][rollbackCount] = true;
//向前跳
if(position + a < 8000 && !set.contains(position + a)){
queue.offer(new int[]{position + a,0});
}
//向后跳
if(position - b >= 0 && !set.contains(position - b) && rollbackCount == 0){
queue.offer(new int[]{position - b,rollbackCount + 1});
}
}
}
return -1;
}
}
边栏推荐
- Common training data set formats for target tracking
- Opencv configuration 2019vs
- typescript ts 基础知识之类型声明
- LocalStorage和SessionStorage
- 如何选择合适的自动化测试工具?
- Laravel5.1 Routing - routing packets
- How does laravel run composer dump autoload without emptying the classmap mapping relationship?
- null == undefined
- Three. JS series (2): API structure diagram-2
- LeetCode 1986. 完成任务的最少工作时间段 每日一题
猜你喜欢
随机推荐
面向接口编程
Opencv configuration 2019vs
面试题 01.02. 判定是否互为字符重排-辅助数组算法
Deep listening array deep listening watch
如何选择合适的自动化测试工具?
Geoserver2.18 series (5): connect to SQLSERVER database
【医学分割】attention-unet
typescript ts基础知识之tsconfig.json配置选项
Record the migration process of a project
打造All-in-One应用开发平台,轻流树立无代码行业标杆
logback.xml配置不同级别日志,设置彩色输出
Advanced C language -- function pointer
LeetCode 1774. 最接近目标价格的甜点成本 每日一题
【DesignMode】外观模式 (facade patterns)
【MySql进阶】索引详解(一):索引数据页结构
Balanced binary tree (AVL)
How can laravel get the public path
OpenGL personal notes
《产品经理必读:五种经典的创新思维模型》的读后感
Cesium (4): the reason why gltf model is very dark after loading