1654. 到家的最少跳跃次数
题意
- 可以左跳可以右跳
- 不能连续左跳两次
- 不能跳到负数
- 不能跳到
forbidden[]
- 求可以跳到
x
的最少跳跃次数
code
a. overview
最初时,只有 0 位置可以进行跳跃;在跳到 a 位置后,又可以跳到 2a 位置和 a-b 位置(如果 a>b);然后又多了两个位置(或者一个位置)可以跳跃…因此这是一个广度优先搜索问题。
在搜索时,要注意:
- 不能连续左跳两次(因此要记录上一跳的状态)
- 不能跳到负数
- 不能跳到
forbidden[]
b. 上限问题
虽然题目中确定了下限(为 0 ),但是没有显示说明上限,因此这里进行分类讨论:
- a = b。左跳可以抵消右跳,因此为了最短跳跃次数,应当一直右跳,因此上限为
x
(若超过 x 还没到达,则永远到达不了); - a > b。由于不能连续两次左跳,因此一定是一直前进,上限为
x + b
(若超过 x + b 还没到达,则永远回不到 x + b); - a < b。上限为
max(max(forbidden) + a + b, x)
。证明见力扣,看不懂。 实际做题的时候设为 6000 也能过。
一直超时,最后发现,只有当 dp[cur] + 1 < dp[cur + a]
或 dp[cur] + 1 < dp[cur - b]
(也就是发现了到达该点的更少的跳跃次数) 时才需要进行更新,这样会减少很多冗余的处理。文章来源:https://www.toymoban.com/news/detail-685852.html
class Solution {
public:
int MAXN = 1e9+10;
int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
int f = *max_element(forbidden.begin(), forbidden.end());
int bound = max(x + b, a + b + f);
vector<int> dp(bound + 1, MAXN); // 初始化为 MAXN,表示一开始所有点没有到达,方便后面更新最小跳跃次数
vector<int> direct(bound + 1, 0); // 记录跳跃方向
queue<int> q;
dp[0] = 0; // 0 位置跳跃 0 次即可到达
direct[0] = 1; // 0 位置只能向右跳
for(int i = 0; i < forbidden.size(); i++) // forbidden 都不能到达
{
dp[forbidden[i]] = -1;
}
if(dp[0] == -1) return -1;
q.push(0);
int curLayerCnt = 1; // 为了计数跳跃次数,这里做了一个记录层数的层次遍历
int layer = 0;
while(!q.empty())
{
int preLayerCnt = curLayerCnt;
curLayerCnt = 0;
while(preLayerCnt)
{
int cur = q.front();
q.pop();
preLayerCnt--;
if(cur == x) return layer;
// 处理当前点可到达的点
// 不能连续向后跳两次,所以要记录跳的方向
if(direct[cur] == 1)
{
// 上一次向右跳,可以向左跳
if(cur >= b && dp[cur - b] != -1) // 没超下限 且 可到达 -》向左跳
{
if(dp[cur] + 1 < dp[cur - b]) // 如果有更少的跳跃次数,才更新
{
direct[cur - b] = -1;
dp[cur - b] = dp[cur] + 1;
curLayerCnt++;
q.push(cur - b);
}
}
}
// 上一跳无论什么方向都可以向右跳
if(cur + a <= bound && dp[cur + a] != -1 && dp[cur] + 1 < dp[cur + a])
{
dp[cur + a] = dp[cur] + 1;
curLayerCnt++;
q.push(cur + a);
direct[cur + a] = 1;
}
}
//cout<<layer<<" ";
layer++;
}
return -1;
}
};
复杂度
时间复杂度:O(max(max(forbidden) + a + b, x))
空间复杂度:O(max(max(forbidden) + a + b, x))文章来源地址https://www.toymoban.com/news/detail-685852.html
到了这里,关于【LeetCode - 每日一题】1654. 到家的最少跳跃次数(23.08.30)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!