`

Jump Game II

 
阅读更多
Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

[分析] 自己的暴力方法仍然超时,搬大牛的解法,能理解正确性但目测现在还不能类似地举一反三,多练习几遍,我想慢慢会领悟其中的奥妙。

[ref]
1. http://blog.csdn.net/linhuanmars/article/details/21356187
2. 很生动的解释:http://www.cnblogs.com/lichen782/p/leetcode_Jump_Game_II.html
public class Solution {
    // Method 2: O(n)
    // http://blog.csdn.net/linhuanmars/article/details/21356187
    public int jump(int[] nums) {
        if (nums == null || nums.length <= 1)
            return 0;
        int N = nums.length;
        int lastReach = 0, reach = 0;
        int steps = 0;
        for (int i = 0; i <= reach && i < N; i++) {
            if (i > lastReach) {
                steps++;
                lastReach = reach;
            }
            reach = Math.max(reach, i + nums[i]);
        }
        return steps;
    }
    // Method 1: timeout
    public int jump1(int[] nums) {
        if (nums == null || nums.length <= 1)
            return 0;
        int N = nums.length;
        int[] dp = new int[N];
        dp[0] = 0;
        for (int i = 1; i < N; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (j + nums[j] >= i)
                    dp[i] = Math.min(dp[i], dp[j] + 1);
            }
        }
        if (dp[N - 1] < Integer.MAX_VALUE)
            return dp[N - 1];
        else
            return -1;
    }
}
分享到:
评论

相关推荐

    java-leetcode题解之Jump Game II.java

    Java题解之Jump Game II涉及编写一个Java程序来解决LeetCode上的Jump Game II问题。在这个Java程序中,我们可以使用贪心算法的解法,每次都在当前可跳范围内找到能跳到最远位置的点作为下一步的目标,以此来保证跳跃...

    C语言-leetcode题解之45-jump-game-ii.c

    其中,编号为45的题目“Jump Game II”要求参与者编写一个函数,实现找到从数组的起始位置到达最后一个位置最少跳跃次数的算法。这个题目虽然简单,但是非常考验程序员的逻辑思维和算法设计能力。 在解决这个问题的...

    fuxuemingzhu#Leetcode-Solution-All#55. Jump Game 跳跃游戏1

    1.贪心算法中,作出的每步贪心决策都无法改变,因为贪心策略是由上一步的最优解推导下一步的最优解,而上一步之前的最优解则不作保留 2.由(1)中的介绍,可以知道贪

    wechat_jump_game-master.rar_Jump!_安卓 模拟_安卓模拟器_跳一跳安卓_跳一跳辅助

    从“wechat_jump_game-master.rar”的文件名中可以推测,这个压缩包包含的可能是这个辅助工具项目的主代码库或源代码文件夹。在成功解压后,用户或许会发现其中包含了各类代码文件、配置文件和使用说明文档等。这些...

    jumpgame源码

    jumpgame untiy项目源码

    wechat_jump_game-master.zip_JUMP_py_wechat_jump_game_跳一跳

    而“wechat_jump_game-master.zip_JUMP_py_wechat_jump_game_跳一跳”这个压缩包,提供了一个用Python编写的自动游玩“跳一跳”的源代码,对于想要学习自动化控制、图像识别和游戏策略的开发者来说,是一份宝贵的...

    java-leetcode题解之Jump Game.java

    在Java中,LeetCode题解之Jump Game是解决算法问题的一个典型示例,此题目通常被归纳为贪心算法的范畴。该问题主要关注的是在一个数组中,规定了每次可以跳的最大步数,判断从起始位置是否能够到达数组的最后一个...

    c++-c++编程基础之leetcode题解第45题跳跃游戏II.zip

    第45题“跳跃游戏II”(Jump Game II)是一道典型的动态规划问题,它要求我们找到在给定数组中达到最后一个元素的最小跳跃次数。在这道题目中,每个元素代表我们可以前进的最大步数,我们需要找到一个最优策略来最小...

    wechat_jump_game-master.zip_python 小游戏_wechat. jump game_wechat_

    【微信跳一跳小游戏Python实现详解】 微信跳一跳是一款风靡一时的微信小程序游戏,玩家需要控制小人精准地跳跃到每个平台上,积累分数。本文将深入探讨如何使用Python编程语言来自动化实现微信跳一跳的小游戏过程。...

    jump-game.rar_Jump!

    "Jump!",这个简单的标题暗示着我们即将探讨的是一个关于跳跃的游戏,而“jump!”标签则进一步强调了游戏的核心机制。在这个名为"跳跃游戏"的压缩包文件中,我们可以期待找到一系列用于创建这样一个游戏的资源和代码...

    java-leetcode题解之055-Jump-Game

    java入门 java_leetcode题解之055_Jump_Game

    leetcode代码200题c++

    4. **Jump Game II**:此问题涉及到广度优先搜索(BFS)或深度优先搜索(DFS)策略,以找出在给定限制下到达最远位置的跳跃次数。它考察了图遍历和优化算法性能的能力。 5. **Sliding Window Maximum**:这是一个...

    wechat_jump_game-master.rar_JUMP_obd_sawhog_跳一跳

    标题中的“wechat_jump_game-master.rar_JUMP_obd_sawhog_跳一跳”表明这是一个关于微信小游戏“跳一跳”的自动化脚本项目。这个项目利用了OBD(Observed Board Data)和Sawhog算法来实现游戏的自动控制,帮助用户在...

    45jumpgame2.cpp

    leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题leetcode45题

    C语言-leetcode题解之55-jump-game.c

    最后,需要注意的是,由于本题的输入和输出都是标准的数据结构,我们不需要在主函数中添加额外的读取和打印代码,只需要调用jumpGame函数,并传入相应的参数即可。 总的来看,这道题是对贪心算法理解和实现能力的一...

    _leetcode-python.pdf

    - Jump Game / Jump Game II: 第一个问题要求判断是否能到达数组的最后一个位置,第二个问题要求求出最小跳跃次数到达最后一个位置。 - Permutations / Permutations II: 生成所有可能的排列组合,考虑重复元素的...

    js-leetcode题解之45-jump-game-ii.js

    题目45题,即“跳跃游戏 II”,要求给定一个非负整数数组,其中每个元素表示在该位置上跳跃的最大长度,问最少需要跳跃多少次能够到达数组的最后一个位置。 在解决这个问题之前,需要掌握一些关键的算法概念。首先...

    jumpGame仿简易版跳一跳.rar

    本简易版 跳一跳使用Cocos来完成编写。 (使用js进行逻辑编写) 对应csdn博客链接:https://blog.csdn.net/weixin_43388844/article/details/96730842

Global site tag (gtag.js) - Google Analytics