当前位置:网站首页>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;
}
}
边栏推荐
- LeetCode 1654. 到家的最少跳跃次数 每日一题
- 3000 words speak through HTTP cache
- Pycharm terminal enables virtual environment
- Vs2019 configuration matrix library eigen
- 谎牛计数(春季每日一题 53)
- Read PG in data warehouse in one article_ stat
- 运算符
- Personal notes of graphics (4)
- 掌握这套精编Android高级面试题解析,oppoAndroid面试题
- Advanced C language -- function pointer
猜你喜欢
随机推荐
Spark Tuning (III): persistence reduces secondary queries
Pycharm terminal enables virtual environment
Lie cow count (spring daily question 53)
Skimage learning (3) -- gamma and log contrast adjustment, histogram equalization, coloring gray images
打造All-in-One应用开发平台,轻流树立无代码行业标杆
【DesignMode】模板方法模式(Template method pattern)
Cesium(3):ThirdParty/zip. js
skimage学习(3)——使灰度滤镜适应 RGB 图像、免疫组化染色分离颜色、过滤区域最大值
Lowcode: four ways to help transportation companies enhance supply chain management
Master this promotion path and share interview materials
LeetCode 300. 最长递增子序列 每日一题
【Seaborn】组合图表、多子图的实现
面试题 01.02. 判定是否互为字符重排-辅助数组算法
直接上干货,100%好评
Localstorage and sessionstorage
《产品经理必读:五种经典的创新思维模型》的读后感
应用在温度检测仪中的温度传感芯片
AutoLISP series (3): function function 3
字节跳动Android金三银四解析,android面试题app
Module VI