深圳网站建设找哪,vi手册,网站改版seo,wordpress 个人站文章目录1. 题目2. 解题1. 题目
有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发#xff0c;到达它的家。
跳蚤跳跃的规则如下#xff1a;
它可以 往前 跳恰好 a 个位置#xff08;即往右跳#xff09;。它可以 往后 跳恰好 b 个位置#xff08;即往左跳到达它的家。
跳蚤跳跃的规则如下
它可以 往前 跳恰好 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.com/problems/minimum-jumps-to-reach-home 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
广度优先搜索搜索的位置需要比 x 大一些然后往回跳的时候注意不用标记已经访问过往前跳的时候标记访问即可
class Solution {
public:int minimumJumps(vectorint forbidden, int a, int b, int x) {int endpos x4000;vectorbool vis(endpos, false);unordered_setint fib(forbidden.begin(), forbidden.end());vis[0] true;queuepairint,bool q;q.push({0,false});//位置上一次是向后的吗int step 0, size;while(!q.empty()) {size q.size();while(size--){int p q.front().first;bool back q.front().second;if(p x)return step;q.pop();if(pa endpos !fib.count(pa) !vis[pa]){vis[pa] true;q.push({pa, false});}if(p-b 0 !fib.count(p-b) !vis[p-b] !back){// vis[p-b] true; //不能写q.push({p-b, true});}}step;}return -1;}
};56 ms 14.7 MB
或者一个位置使用两个访问标记前向的和后向的
class Solution {
public:int minimumJumps(vectorint forbidden, int a, int b, int x) {int endpos x4000;vectorvectorbool vis(endpos, vectorbool(2,false));unordered_setint fib(forbidden.begin(), forbidden.end());vis[0][0] vis[0][1] true;queuepairint,bool q;q.push({0,false});//位置上一次是向后的吗int step 0, size;while(!q.empty()) {size q.size();while(size--){int p q.front().first;bool back q.front().second;if(p x)return step;q.pop();if(pa endpos !fib.count(pa) !vis[pa][0]){vis[pa][0] true;q.push({pa, false});}if(p-b 0 !fib.count(p-b) !vis[p-b][1] !back){vis[p-b][1] true; q.push({p-b, true});}}step;}return -1;}
};404 ms 49.2 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
