当前位置:网站首页>LeetCode 1654. The minimum number of jumps to get home one question per day
LeetCode 1654. The minimum number of jumps to get home one question per day
2022-07-07 16:59:00 【@Little safflower】
Problem description
There's a flea's home on the axis x It's about . Please help it from the position 0 set out , Get to its home .
The rules of flea jumping are as follows :
It can forward Jump just right a A place ( Jump right ).
It can Back up Jump just right b A place ( Jump to the left ).
It can't continuity Jump back 2 Time .
It can't jump to anything forbidden Position in array .
Fleas can jump forward exceed The location of its home , But it is You can't jump to negative integers The location of .Give you an array of integers forbidden , among forbidden[i] It's where fleas can't jump , At the same time give you the whole number a, b and x , Please return to the flea's home for the minimum number of jumps . If it doesn't just arrive x Feasible plan of , Please return -1 .
Example 1:
Input :forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
Output :3
explain : Jump forward 3 Time (0 -> 3 -> 6 -> 9), Fleas are home .
Example 2:Input :forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
Output :-1
Example 3:Input :forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
Output :2
explain : Jump forward once (0 -> 16), And then jump back (16 -> 7), Fleas are home .
Tips :
1 <= forbidden.length <= 1000
1 <= a, b, forbidden[i] <= 2000
0 <= x <= 2000
forbidden All the positions in are different from each other .
Location x be not in forbidden in .source : Power button (LeetCode)
link :https://leetcode.cn/problems/minimum-jumps-to-reach-home
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Java
class Solution {
public int minimumJumps(int[] forbidden, int a, int b, int x) {
// Record the forbidden locations
Set<Integer> set = new HashSet<>();
for(int forbid : forbidden) set.add(forbid);
Queue<int[]> queue = new LinkedList<>();// The current position , Number of backward jumps
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;
// Jump forward
if(position + a < 8000 && !set.contains(position + a)){
queue.offer(new int[]{position + a,0});
}
// Jump back
if(position - b >= 0 && !set.contains(position - b) && rollbackCount == 0){
queue.offer(new int[]{position - b,rollbackCount + 1});
}
}
}
return -1;
}
}
边栏推荐
- AutoLISP series (1): function function 1
- URL和URI的关系
- 水平垂直居中 方法 和兼容
- 《产品经理必读:五种经典的创新思维模型》的读后感
- LeetCode 120. Triangle minimum path and daily question
- Sqlserver2014+: create indexes while creating tables
- LeetCode 1696. 跳跃游戏 VI 每日一题
- Usage of config in laravel
- Prometheus API deletes all data of a specified job
- Pisa-Proxy SQL 解析之 Lex & Yacc
猜你喜欢
【DesignMode】外观模式 (facade patterns)
[Android -- data storage] use SQLite to store data
Spark Tuning (III): persistence reduces secondary queries
QT中自定义控件的创建到封装到工具栏过程(一):自定义控件的创建
预售17.9万,恒驰5能不能火?产品力在线,就看怎么卖
AutoLISP series (1): function function 1
1亿单身男女“在线相亲”,撑起130亿IPO
C语言进阶——函数指针
The team of East China Normal University proposed the systematic molecular implementation of convolutional neural network with DNA regulation circuit
Interface oriented programming
随机推荐
[designmode] template method pattern
SqlServer2014+: 创建表的同时创建索引
logback. XML configure logs of different levels and set color output
作为Android开发程序员,android高级面试
skimage学习(3)——使灰度滤镜适应 RGB 图像、免疫组化染色分离颜色、过滤区域最大值
两类更新丢失及解决办法
LeetCode 1155. 掷骰子的N种方法 每日一题
3000 words speak through HTTP cache
Talk about the realization of authority control and transaction record function of SAP system
爬虫(17) - 面试(2) | 爬虫面试题库
最新高频Android面试题目分享,带你一起探究Android事件分发机制
最新Android高级面试题汇总,Android面试题及答案
A tour of gRPC:03 - proto序列化/反序列化
The process of creating custom controls in QT to encapsulating them into toolbars (II): encapsulating custom controls into toolbars
C语言进阶——函数指针
Master this set of refined Android advanced interview questions analysis, oppoandroid interview questions
Prometheus API deletes all data of a specified job
Spark Tuning (III): persistence reduces secondary queries
深度监听 数组深度监听 watch
【PHP】PHP接口继承及接口多继承原理与实现方法