郑州校园兼职网站建设,临沂中文网站建设,深圳网站建设公司元,wordpress开启子目录多站点模式#xff08;leetcode1654#xff09;到达家的最少跳跃次数-------------------Java实现
题目表述
某个 bug 的家位于 x 轴上的位置x。帮助他们从位置到达那里0。
bug按照以下规则跳转#xff1a;
它可以向前#xff08;向右#xff09;精确跳跃a位置。 它可以精确地向…leetcode1654到达家的最少跳跃次数-------------------Java实现
题目表述
某个 bug 的家位于 x 轴上的位置x。帮助他们从位置到达那里0。
bug按照以下规则跳转
它可以向前向右精确跳跃a位置。 它可以精确地向后向左跳跃b位置。 它不能连续向后跳两次。 它不能跳转到任何forbidden位置。 该错误可能会向前跳转到其所在位置之外但它无法跳转到以负整数编号的位置。
给定一个整数数组forbidden其中forbidden[i]表示 bug 无法跳转到该位置forbidden[i]而整数a、b和 则x返回bug 到达其起始位置所需的最小跳转次数。如果没有可能的跳跃序列使 bug 到达位置x则返回-1.
样例
示例1
输入 forbidden [14,4,18,1,15], a 3, b 15, x 9 输出 3 解释向前跳转 3 (0 - 3 - 6 - 9) 将得到虫子回家。 示例2
输入禁止 [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) 将把 bug 带回家。
条件
1 forbidden.length 1000 1 a, b, forbidden[i] 2000 0 x 2000 中的所有元素forbidden都是不同的。 位置x不被禁止。
思路
此题感觉最大的难点在对于最大值的判断和选择的问题上确定了最大值的问题用广搜就能解决。 最大值问题标准答案 思路 看题目解答。
注意点
这题对于思路的判断是要精准的确定是广搜的解决思路因为要确定最优解而且如果不加限制的进行递归操作堆栈很大而且不好限制路数。 最大值判断个人感觉难度过大。 可以用2000ab(因为超出的部分肯定需要返回才能到达而且返回只能单次进行所以)代替就是速度慢一点。
ac代码
c:
class Solution {public int minimumJumps(int[] forbidden, int a, int b, int x) {Queueint[] queue new ArrayDequeint[]();SetInteger visited new HashSetInteger();SetInteger forbiddenset new HashSetInteger();visited.add(0);int now_sit,dirction,step;int max 2000ab;for(int i : forbidden)forbiddenset.add(i);int[] q new int[]{0,1,0};queue.add(q);while(!queue.isEmpty()){q queue.poll();if (q[0]x)return q[2];dirction q[1];stepq[2];now_sitq[0]a;if (now_sit0now_sitmax!visited.contains(now_sit)!forbiddenset.contains(now_sit)){queue.offer(new int[]{now_sit,1,step1});visited.add(now_sit);}now_sitq[0]-b;if (now_sit0now_sitmaxdirction1!visited.contains(-now_sit)!forbiddenset.contains(now_sit)) {queue.offer(new int[]{now_sit, 0, step 1});visited.add(-now_sit);}}return -1;}}来源力扣LeetCode 链接https://leetcode-cn.com/problems/squares-of-a-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
