app网站开发住房公积金,大龄工找工作哪个网站好,个网站做淘宝客推广可以吗,手机版免费申请微网站目录
题目#xff1a;
示例#xff1a;
分析#xff1a;
代码#xff1a; 题目#xff1a; 示例#xff1a; 分析#xff1a;
题目给我们一只跳蚤#xff0c;我们可以操控它前跳 a 格或是后跳 b 格#xff0c;不能跳到小于0的位置#xff0c;有一些被禁止的点不…目录
题目
示例
分析
代码 题目 示例 分析
题目给我们一只跳蚤我们可以操控它前跳 a 格或是后跳 b 格不能跳到小于0的位置有一些被禁止的点不能跳到也不能连续后跳两次问我们最少跳几次可以让它回家。
一般寻找最短路径我们是用BFS的不过我更喜欢DFS所以我这边使用DFS不过大体的思路是一样的懂得怎么操作之后两种方法都是可以自己写出来的。
要写出DFS不难但是有三个点要注意。
第一点是不能连续后跳两次所以我们传入递归函数的参数中需要记录上一次是前跳还是后跳。因为不能连续后跳两次所以如果上一次是后跳那么我们本次递归就只能前跳。如果上一次是前跳那我们本次递归就可以后跳以及前跳。
第二点是边界范围题目要求不能跳到小于0的位置所以左边界是0。而右边界由于我们可以跳到目标点的后面再后跳回来所以我们右边界不能定为目标点。我原本以为一次最多就后跳b格所以我把右边界设为了目标值b但是是行不通的。最终右边界设置为6000就可以了因为题目有给出限制目标点、a、b最大都是2000那么把他们加起来就是6000稍微思考一下就可以知道在最极端的情况下我们也不需要跳到6000往后的点所以右边界设为6000即可。 不过还是有大佬把右边界的具体范围推导出来了比较复杂感兴趣的小伙伴可以自行去本题的题解里查看。 最后一点就是剪枝因为我们可能会跳到重复的一个点进而陷入死循环所以我们需要在递归的时候将往前跳的落脚点设为被禁止的点这样就不会重复跳到同一个点了。
不过往后跳的点不需要因为如果是后跳跳到了一个点那么接下来就只能是往前跳了。如果设置为了禁止点那么如果后续递归中是往前跳跳到了这个点那么本来是可以在这个点上往后跳的但是由于设置为了禁止点所以就会退出循环这样就少了一种可能性也就有可能会错失答案。 可能会有小伙伴会有疑问后跳的点不设为禁止点不会进入死循环吗
答案是不会的因为如果下次是前跳到这个点了那么还是会被设为禁止点。然而是不可能是后跳到重复的点因为不能重复后跳两次能够后跳到这个点的地方一定是前跳到那个地方的也就是会被设为禁止点那么也就不可能再重复后跳到同一个点了。
所以本质上是让一个点最多能重复跳到两次第一次是后跳到达最后一次是前跳到达。
代码
class Solution {
public:int resINT_MAX;void find(unordered_setintforbidden,int a,int b,int cur,int x,int temp,bool flag){if(cur0||cur6000||tempres) return; //设置边界if(curx){resmin(res,temp);return;}//前跳if(!forbidden.count(cura)){ //如果下一个跳跃点不被禁止,那么跳跃forbidden.insert(cura); //避免进入死循环,将跳跃点设为禁止点find(forbidden,a,b,cura,x,temp1,true);}//后跳if(!forbidden.count(cur-b)flag){ //如果后跳的点不被禁止,并且上一次不是后跳,那么跳跃find(forbidden,a,b,cur-b,x,temp1,false);//不将后跳的点设为禁止点,可能会错过答案.因为}}int minimumJumps(vectorint forbidden, int a, int b, int x) {unordered_setints(forbidden.begin(),forbidden.end()); //将禁止点集合转为set方便查询find(s,a,b,0,x,0,true);return resINT_MAX?-1:res;}
};
