当前位置：首页 > article >正文

贪心算法（10）（java）跳跃游戏

article 2025/3/22 5:27:53

题目：

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

解法：1.贪心策略（不推荐）

2，层序遍历。

public class Solution {
    public int jump(int[]nums){
        int left=0,right=0,maxPos=0,n= nums.length,ret=0;
        while (left<=right){//以防跳不到n-1的位置
            if(maxPos>=n-1)//判断是否以经跳到最后一个位置
            {
                return ret;
            }
            for (int i=left;i<=right;i++)//更新下一层最右端点
            {
                maxPos=Math.max(maxPos,nums[i]+i);

            }
            left=right+1;
            right=maxPos;
            ret++;
        }
        return -1;
    }

    public static void main(String[] args) {
        Solution solution=new Solution();
        int []nums={2,3,1,1,4};
        System.out.println(solution.jump(nums));
    }
}

查看全文

http://www.kler.cn/a/594940.html