一、题目
有一只跳蚤的家在数轴上的位置 x
处。请你帮助它从位置 0
出发,到达它的家。
跳蚤跳跃的规则如下:
- 它可以 往前 跳恰好
a
个位置(即往右跳)。 - 它可以 往后 跳恰好
b
个位置(即往左跳)。 - 它不能 连续 往后跳
2
次。 - 它不能跳到任何
forbidden
数组中的位置。 - 跳蚤可以往前跳超过它的家的位置,但是它不能跳到负整数的位置。
给你一个整数数组 forbidden
,其中 forbidden[i]
是跳蚤不能跳到的位置,同时给你整数 a
, b
和 x
,请你返回跳蚤到家的最少跳跃次数。如果没有恰好到达 x
的可行方案,请你返回 -1
。
示例一:
输入:forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
输出:3
解释:往前跳 3 次(0 -> 3 -> 6 -> 9),跳蚤就到家了。
示例二:
输入:forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
输出:-1
示例三:
输入:forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
输出:2
解释:往前跳一次(0 -> 16),然后往回跳一次(16 -> 7),跳蚤就到家了。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/minimum-jumps-to-reach-home/
题目著作权归领扣网络所有。仅供个人学习,非商用。
二、题解与代码
class Solution {
public int minimumJumps(int[] forbidden, int a, int b, int x) {
Queue<int[]> queue = new ArrayDeque<int[]>();
Set<Integer> visited = new HashSet<Integer>();
queue.offer(new int[]{0, 1, 0});
visited.add(0);
int lower = 0, upper = Math.max(Arrays.stream(forbidden).max().getAsInt() + a, x) + b;
Set<Integer> forbiddenSet = new HashSet<Integer>();
for (int position : forbidden) {
forbiddenSet.add(position);
}
while (!queue.isEmpty()) {
int[] arr = queue.poll();
int position = arr[0], direction = arr[1], step = arr[2];
if (position == x) {
return step;
}
int nextPosition = position + a;
int nextDirection = 1;
if (lower <= nextPosition && nextPosition <= upper && !visited.contains(nextPosition * nextDirection) && !forbiddenSet.contains(nextPosition)) {
visited.add(nextPosition * nextDirection);
queue.offer(new int[]{nextPosition, nextDirection, step + 1});
}
if (direction == 1) {
nextPosition = position - b;
nextDirection = -1;
if (lower <= nextPosition && nextPosition <= upper && !visited.contains(nextPosition * nextDirection) && !forbiddenSet.contains(nextPosition)) {
visited.add(nextPosition * nextDirection);
queue.offer(new int[]{nextPosition, nextDirection, step + 1});
}
}
}
return -1;
}
}
作者:力扣官方题解
链接:https://leetcode.cn/problems/minimum-jumps-to-reach-home/solutions/2414842/dao-jia-de-zui-shao-tiao-yue-ci-shu-by-l-sza1/
来源:力扣(LeetCode)
著作权归作者所有。仅供个人学习,非商用。
三、神奇的BUG
注:本部分仅阐述发现的 BUG,本部分代码并不是题解。
3.1 无法执行的 return 和 break 语句
- 在 LeetCode 的官网上,下图红框内的
if
语句在判断结果为true
的条件下不会执行代码块中的return
语句!!! - 在下图中可以很清楚地看到
(tmp[0] == x)
在第 4 次循环时,输出的结果为true
,但并没有执行return
操作。 - 把
Solution
类的代码 直接复制 到 IDEA 中则可以执行!!!
- IDEA 中的执行结果如下图所示:
- 将
return
换成break
语句也同样无法执行:
大家有遇到过类似的 BUG 吗?还是说有什么我没注意到的问题呢?
3.2 通过另一个 break 解决
- 在同层次的另一个
if
语句的代码块中加入break
语句后,之前不能执行的break
和return
语句可以正常执行了!!!
- 严谨起见,我们用如下代码来查看到底是通过哪条语句的
break
退出循环的。 - 显然是之前不能执行的那条。
文章来源:https://www.toymoban.com/news/detail-693176.html
- 当然,新加入的
break
也是可执行的。
文章来源地址https://www.toymoban.com/news/detail-693176.html
到了这里,关于【LeetCode】1654:到家的最少跳跃次数的解题思路 & 关于力扣无法return的BUG的讨论的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!