leetcode:45.跳跃游戏 II

简介: 给定一个非负整数数组,你最初位于数组的第一个位置。

题目描述:


给定一个非负整数数组,你最初位于数组的第一个位置。


数组中的每个元素代表你在该位置可以跳跃的最大长度。


你的目标是使用最少的跳跃次数到达数组的最后一个位置。


示例:


输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。


说明:


假设你总是可以到达数组的最后一个位置。


题目难度:困难


分析


典型的贪心算法,只需要知道当前跳跃的步数,还有跳跃完下一次能跳跃的步数最大值即可,两者相加就是贪心算法的最大值。此时也就是每一步应该跳跃的步数。


代码如下:


class Solution {
    public int jump(int[] nums) {
      // i:数组下标,n:跳跃次数
        int length = nums.length, i = 0, n = 0;
        // 测试用例,如果长度为1直接返回0即可
        if (length == 1) {
            return 0;
        }
        // 当条件满足时代表暂时还没有跳跃到数组最后
        while (i < length - 1) {
            int temp = nums[i];
            // 如果数组的值为1,说明只能跳一步,直接判断完即可
            if (temp == 1) {
                i++;
                n++;
                continue;
            }
            // 如果数组的值大于等于数组剩余的元素个数,说明可以一次性跳完
            if (temp >= length - i - 1) {
                return n + 1;
            }
            // max:在1~temp之间跳跃后的最大值,也就是当前范围内数组元素的最大值
            int max = 0;
            // jump:应该跳的步数
            int jump = 0;
            for (int j = 1; j <= temp; j++) {
                int temp2 = nums[i + j];
                // 这里是跳跃后元素的值+跳跃的步数=贪心算法的最大值
                // 不能光考虑跳跃后元素的值
                if (temp2 + j >= max) {
                    max = temp2 + j;
                    jump = j;
                }
            }
            // 执行跳跃,并且步数+1
            i += jump;
            n++;
        }
        return n;
    }
}


总结:


贪心算法是很经典的解决背包类问题的算法,在各大算法书中几乎都有提到,也是需要掌握的算法之一。

目录
相关文章
|
4天前
|
算法
LeetCode第55题跳跃游戏
LeetCode第55题"跳跃游戏"的解题方法,通过记录当前最远可达到的位置并判断每个位置是否可达以及能否到达末尾,有效解决了跳跃至数组末尾的可行性问题。
LeetCode第55题跳跃游戏
|
11天前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
26 1
|
14天前
|
Python
【Leetcode刷题Python】174. 地下城游戏
LeetCode 174题 "地下城游戏" 的Python解决方案,使用动态规划算法计算骑士从左上角到右下角拯救公主所需的最低初始健康点数。
28 3
|
15天前
|
算法 索引 Python
【Leetcode刷题Python】55. 跳跃游戏
解决LeetCode "跳跃游戏"问题的Python实现代码,使用了贪心算法的思路。代码中初始化最远可到达位置 max_k,并遍历数组 nums,通过更新 max_k 来记录每次能跳到的最远位置,如果在任何时刻 max_k 大于或等于数组的最后一个索引,则返回 True,表示可以到达数组的末尾;如果当前索引 i 超出了 max_k,则返回 False,表示无法继续前进。时间复杂度为 O(n),空间复杂度为 O(1)。
23 1
|
4天前
|
算法
LeetCode第45题跳跃游戏 II
LeetCode第45题"跳跃游戏 II"的解题方法,通过一次循环和选择每个位置的最大可跳距离,有效减少了跳跃次数,简化了问题。
|
2月前
|
算法
力扣经典150题第三十八题:生命游戏
力扣经典150题第三十八题:生命游戏
15 0
|
2月前
|
算法
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
|
2月前
|
算法 机器人
【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人
【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人
|
13天前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
28 6
|
13天前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
43 2