leetcode(45)跳跃游戏

川长思鸟来 2021-10-18 08:46 342阅读 0赞

跳跃游戏

解题思路：贪心算法+自底向上

class Solution {
        public int jump(int[] nums) {
            int end = 0;
            int maxPosition = 0; 
            int steps = 0;
            for(int i = 0; i < nums.length - 1; i++){      
                maxPosition = Math.max(maxPosition, nums[i] + i); 
                if( i == end){ 
                    end = maxPosition;
                    steps++;
                    if(end>=nums.length - 1){
                        break;
                    }
                }
            }
            return steps;
        }
    }

第二种方法（性能上比第一种算法差很多）

解题思路：贪心算法+自顶向下

class Solution {
        public int jump(int[] nums) {
            int len = nums.length;
            int step = 0;
            int position = len - 1;
            while(position!=0) {
                for(int i=0;i<len-1;i++) {
                    if(nums[i]+i>=position) {
                        position = i;
                        step++;
                        break;
                    }
                }
            }
            return step;
        }
    }

转载于:https://www.cnblogs.com/erdanyang/p/11158633.html

发表评论取消回复

表情：

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

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

相关阅读

相关 leetcode55、45.跳跃游戏 I&II

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

我不是女神ヾ/ 2023年01月23日 13:48/ 0 赞/ 170 阅读

相关【贪心】 LeetCode45. 跳跃游戏 II

题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

小咪咪/ 2022年12月03日 13:22/ 0 赞/ 192 阅读

相关 45. 跳跃游戏 II

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

太过爱你忘了你带给我的痛/ 2022年10月08日 15:24/ 0 赞/ 163 阅读

相关 45. 跳跃游戏 II

[力扣![icon-default.png?t=L892][icon-default.png_t_L892]/images/20220828/372516f793d841769

朴灿烈づ我的快乐病毒、/ 2022年09月15日 00:08/ 0 赞/ 205 阅读

相关 leetcode 45 跳跃游戏II

前言题目：[45.跳跃游戏II][45._II] 参考题解：[跳跃游戏II-力扣官方题解][II-] -------------------- 提交代码如

电玩女神/ 2022年08月28日 09:00/ 0 赞/ 171 阅读

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

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

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

相关 leetcode:45.跳跃游戏 II

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

亦凉/ 2022年04月24日 13:44/ 0 赞/ 202 阅读

相关 leetcode:45. 跳跃游戏 II

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

曾经终败给现在/ 2022年04月12日 14:17/ 0 赞/ 225 阅读

相关 leetcode(45)跳跃游戏

跳跃游戏解题思路：贪心算法+自底向上 class Solution { public int jump(int[] nums) {

川长思鸟来/ 2021年10月18日 08:46/ 0 赞/ 343 阅读

相关 LeetCode55 跳跃游戏、LeetCode45跳跃游戏（进阶版）

LeetCode55 跳跃游戏【题目】给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够

缺乏、安全感/ 2021年09月21日 06:18/ 0 赞/ 322 阅读