力扣:45. 跳跃游戏 II

这篇具有很好参考价值的文章主要介绍了力扣:45. 跳跃游戏 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划:

1.声明一个dp数组来表示到下标i时要跳转的最小次数,同时要个每个dp数组的值赋值为最大。之后初始化dp【0】=0,用for循环来进行遍历下标i和遍历下标i之前的值,判断条件为如果i之前的某个下标跳转的距离>=i时要根新dp【i】的值 ,递推公式为dp【i】=math,min(dp[i],dp[j]+1)。表示在这个跳转范围里dp【i】的值为dp【j】加一。文章来源地址https://www.toymoban.com/news/detail-830837.html

class Solution {
    public int jump(int[] nums) {
        //表示的是跳转到下标为i时要跳转的最小次数
        int [] dp=new int [nums.length];
        //给每个dp数组的值赋值为数组的最大长度
        for(int i=1;i<nums.length;i++){
            dp[i]=nums.length;
        }
        //初始化dp【0】时跳转次数为0
        dp[0]=0;
        //来遍历下标i
        for(int i=1;i<nums.length;i++){
            //遍历下标i之前的值
            for(int j=0;j<i;j++){
                //判断跳转的最远距离只要在这个距离中dp【i】的值就为dp【j】加一
                if(j+nums[j]>=i){
                    dp[i]=Math.min(dp[i],dp[j]+1);
                }
            }
        }
        return dp[nums.length-1];
    }
}

到了这里,关于力扣:45. 跳跃游戏 II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 算法leetcode|45. 跳跃游戏 II(rust重拳出击)

    给定一个长度为 n 的 0 索引整数数组 nums 。初始位置为 nums[0] 。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处: 0 = j = nums[i] i + j n 返回到达 nums[n - 1] 的 最小跳跃次数 。生成的测试用例可以到达 nums[n - 1] 。

    2023年04月15日
    浏览(48)
  • 力扣55. 跳跃游戏(动态规划)

    Problem: 55. 跳跃游戏 我们将问题稍做转换 每次求取当前位置可以走到的最远位置 ,在此基础上我们将最终判断是否能走出整个nums;同时我们要判断 中途会不会遇到某个位置是0使得不能继续走下去 时间复杂度: O ( n ) O(n) O ( n ) ;其中 n n n 为数组nums的大小 空间复杂度: O ( 1

    2024年02月21日
    浏览(56)
  • 跳跃游戏 + 45. 跳跃游戏 II

    给你一个非负整数数组  nums  ,你最初位于数组的  第一个下标  。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标,如果可以,返回  true  ;否则,返回  false  。 示例 1: 示例 2: 解析: 每次遍历,只需要贪心跳到最远即可

    2024年02月04日
    浏览(39)
  • 贪心 55. 跳跃游戏 45.跳跃游戏 II

    题目: 给定非负数组,初始位置在数组第一格,数组值是可以选择的最大跳跃步数,判断能不能达到数组末尾。 示例  1: * 输入: [2,3,1,1,4] * 输出: true * 解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。 示例  2: * 输入: [3,2,1,0,4] * 输出

    2024年03月21日
    浏览(46)
  • 代码随想录:55. 跳跃游戏;45. 跳跃游戏 II

    给定一个非负整数数组  nums  ,你最初位于数组的  第一个下标  。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 示例 1: 示例 2: 其实跳几步无所谓,关键在于可跳的覆盖范围! 不一定非要明确一次究竟跳几步,每次取最

    2023年04月11日
    浏览(47)
  • leetcode 45. 跳跃游戏 II

             本题为 跳跃游戏I 的升级版,保证可以到达终点的情况下,要求出最短的跳跃次数。         还是仿照 跳跃游戏I 的思路,定义一个cover用于记录最大覆盖范围,终止条件是:        cover = nums.size()-1   ,还要定义一个变量 largest 用于记录当前最远覆盖范围的下

    2024年02月14日
    浏览(38)
  • 代码随想录 第三十二天 45.跳跃游戏 II||122.买卖股票的最佳时机 II55. 跳跃游戏

    力扣题目链接(opens new window) 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例  1: 输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位

    2024年02月15日
    浏览(54)
  • LeetCode(力扣)45. 跳跃游戏 IIPython

    https://leetcode.cn/problems/jump-game-ii/description/

    2024年02月09日
    浏览(49)
  • LeetCode45.Jump-Game-II<跳跃游戏II>

    从上次大神那里获得的灵感  这题问的是次数,那么我们需要确保 1,能否跳到终点  2,得到次数. 第一次条获得的是nums[0],那么第一个数就是我们第一次能跳跃的范围.每次在范围里获得最大值.并且次数加一.然后进入下一次范围;即可得到次数;    

    2024年02月15日
    浏览(42)
  • 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日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包