45. Jump Game II

客官°小女子只卖身不卖艺 2022-02-16 19:47 196阅读 0赞

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.
    
    Example:
    
    Input: [2,3,1,1,4]
    Output: 2
    Explanation: 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.
    Note:
    
    You can assume that you can always reach the last index.

public int jump(int[] nums) {
            /**
             * 此处基于贪婪的算法的前提是不管怎么跳都能到达终点，恰巧题目给出这个前提
             * 首先在到达位置0和位置0之前，必须跳跃一次，在到达0的过程中，能到的最远的位置是x;
             * 然后在从1开始到达位置x和位置x之前，必须跳跃一次，此次跳跃能达到的最远位置是...
             * 以此类推
             */
            int jumps = 0, end = 0, farthestDestination = 0;
            for(int i = 0; i < nums.length - 1; ++i) {
                farthestDestination = Math.max(farthestDestination, i + nums[i]);
                if(i == end) {
                    ++jumps;
                    end = farthestDestination;
                }
            }
            return jumps;
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，196人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode 45. Jump Game II (贪心)

目描述：每个点的数字代表可以从当前节点跳跃最远的节点数，比如 \[ 2, 3, 1, 1, 4 \] 第一个节点跳跃最远位置就是下标为2的第三个元素。求跳到最后一...

蔚落/ 2024年04月18日 11:01/ 0 赞/ 67 阅读

相关 leetcode 45. Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index

﹏ヽ暗。殇╰゛Y/ 2022年08月21日 04:44/ 0 赞/ 23 阅读

相关 LeetCode45——Jump Game II

LeetCode45——Jump Game II 题意：在一串序列中，每个索引对应的value表示你能跳的最大步数。你在任何索引处可以跳\[1,value\]步，求跳

刺骨的言语ヽ痛彻心扉/ 2022年08月09日 12:41/ 0 赞/ 22 阅读

相关 LeetCode 55/45 Jump Game I/II-----Greedy**

一：[Jump Game][] 题目： Given an array of non-negative integers, you are initially positio

ゝ一世哀愁。/ 2022年08月07日 12:47/ 0 赞/ 33 阅读

相关 LeetCode 45.Jump Game II (跳跃游戏II)

题目描述: 给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

约定不等于承诺〃/ 2022年05月11日 04:16/ 0 赞/ 215 阅读

相关 45. Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index

妖狐艹你老母/ 2022年03月21日 11:10/ 0 赞/ 176 阅读

相关【Leetcode】45. Jump Game II（动态规划）

Given an array of non-negative integers, you are initially positioned at the first index

待我称王封你为后i/ 2022年02月25日 01:57/ 0 赞/ 217 阅读

相关 45. Jump Game II

Given an array of non-negative integers, you are initially positioned at the first i

客官°小女子只卖身不卖艺/ 2022年02月16日 19:47/ 0 赞/ 197 阅读

相关 45. Jump Game II

description: Given an array of non-negative integers, you are initially positioned at

╰半橙微兮°/ 2021年11月01日 04:46/ 0 赞/ 269 阅读

相关【LeetCode 45 55 1306】Jump Game I，II，III【JAVA】

跳跃游戏，合计三道题。 55. Jump Game 1. 题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_s

桃扇骨/ 2021年09月21日 02:18/ 0 赞/ 307 阅读