【LeetCode - 每日一题】1654. 到家的最少跳跃次数(23.08.30)

这篇具有很好参考价值的文章主要介绍了【LeetCode - 每日一题】1654. 到家的最少跳跃次数(23.08.30)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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](也就是发现了到达该点的更少的跳跃次数) 时才需要进行更新,这样会减少很多冗余的处理。

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode每日一题——45.跳跃游戏II(面试经典150题)

    45. 跳跃游戏 II - 力扣(LeetCode) 给定一个长度为 n 的 0 索引 整数数组 nums。 初始位置为 nums[0] 。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:   0 = j = nums[i]     i + j n 返回到达 nums[n - 1] 的最小跳跃次数

    2024年02月13日
    浏览(43)
  • LeetCode每日一题:2594. 修车的最少时间(2023.9.7 C++)

    目录 2594. 修车的最少时间 题目描述: 实现代码与解析: 二分 原理思路:         给你一个整数数组  ranks  ,表示一些机械工的  能力值  。 ranksi  是第  i  位机械工的能力值。能力值为  r  的机械工可以在  r * n2  分钟内修好  n  辆车。 同时给你一个整数  cars

    2024年02月09日
    浏览(51)
  • 每日一题leetcode--使循环数组所有元素相等的最少秒数

    相当于扩散,每个数可以一次可以扩散到左右让其一样,问最少多少次可以让整个数组都变成一样的数 使用枚举,先将所有信息存到hash表中,然后逐一进行枚举,计算时间长短用看下图  考虑到环形数组,可以把首项+n放到最后,这样for循环就相当于前后可以联通 贴一张别

    2024年02月12日
    浏览(48)
  • 【LeetCode每日一题】2809. 使数组和小于等于 x 的最少时间

    2024-1-19 2809. 使数组和小于等于 x 的最少时间 思路: 获取两个列表的长度n,并初始化一个二维数组f,用于存储最优解。 定义一个二维数组nums,用于存储输入的两个列表中的元素,并按照第二列元素进行排序。 使用动态规划的方法,通过遍历nums数组,计算最优解。其中,

    2024年01月21日
    浏览(49)
  • (数组) 1207. 独一无二的出现次数 ——【Leetcode每日一题】

    难度:简单 给你一个整数数组 arr ,请你帮忙统计数组中每个数的出现次数。 如果每个数的出现次数都是独一无二的,就返回 true ;否则返回 false 。 示例 1: 输入:arr = [1,2,2,1,1,3] 输出:true 解释:在该数组中,1 出现了 3 次,2 出现了 2 次,3 只出现了 1 次。没有两个数的出

    2024年02月08日
    浏览(42)
  • 每日一题——LeetCode1287.有序数组中出现次数超过25%的元素

    方法一 一次循环统计 题目给出的数据相同的元素都是相邻的,那么直接从头开始遍历,统计每种元素出现次数,当有元素次数超过arr.length/4即为要求的元素   消耗时间和内存情况: 方法二 方法一简化版 设步长step=arr.length/4,如果某个元素arr[i],跨越一个步长后arr[i+step],即

    2024年01月22日
    浏览(52)
  • 2023-06-14 LeetCode每日一题(二进制字符串前缀一致的次数)

    点击跳转到题目位置 给你一个长度为 n 、下标从 1 开始的二进制字符串,所有位最开始都是 0 。我们会按步翻转该二进制字符串的所有位(即,将 0 变为 1)。 给你一个下标从 1 开始的整数数组 flips ,其中 flips[i] 表示对应下标 i 的位将会在第 i 步翻转。 二进制字符串 前缀

    2024年02月08日
    浏览(54)
  • 【每日一题】Leetcode - 剑指 Offer 43. 1~n 整数中 1 出现的次数

    Leetcode - 剑指 Offer 43. 1~n 整数中 1 出现的次数 分解数字中的每一位,判断+记录 = 结果 But,超时了,下面是优化过程简介 空间换时间(爆内存) :n = 123456,则n{len-1} = 12345,其实走到n这里,说明n{len-1}这个数字我们一定已经知道了它有多少个1了,所以我们只需要记录保存下

    2024年02月11日
    浏览(49)
  • 【LeetCode每日一题】2645. 构造有效字符串的最少插入数(计算组数+动态规划+考虑相邻字母)

    2024-1-11 2645. 构造有效字符串的最少插入数 方法一:计算组数 1.用count统计,能构成几组abc 2.如果当前字符大于之前字符,说明还在组内,不更新 3.如果当前字符小于等于之前字符,说明不是同一组的abc,组数更新 4.最终返回值:组数*3,再减去原本的字符数,就是要插入的次数

    2024年01月17日
    浏览(59)
  • 2023-08-23 LeetCode每日一题(统计点对的数目)

    点击跳转到题目位置 给你一个无向图,无向图由整数 n ,表示图中节点的数目,和 edges 组成,其中 edges[i] = [u i , v i ] 表示 u i 和 v i 之间有一条无向边。同时给你一个代表查询的整数数组 queries 。 第 j 个查询的答案是满足如下条件的点对 (a, b) 的数目: a b cnt 是与 a 或者 b

    2024年02月11日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包