Leetcode第45题(跳跃游戏II)

简介: 这篇博客文章讨论了如何使用贪心算法解决LeetCode第45题“跳跃游戏II”,目的是找到使用最少跳跃次数到达数组末尾的策略。

题目描述:

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

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

使用 i 遍历数组,每次维护一个从当前位置所能走到的最远位置的区域,当 i 为 0 时,maxPos所能到达的最远下标maxPos = max(0,nums[0] + 0) = 2,当 i == rightPos时,表示 i 已经走到了一步能走到的最远处,此时需要走到下一个区域,因此步数stepAns++,同时更新右边界rightPos = maxPos = 2。

当 i 为 2 时,maxPos所能到达的最远下标maxPos = max(4,nums[2] + 2) = 4,当 i == rightPos时,表示 i 已经走到了一步能走到的最远处,此时需要走到下一个区域,因此步数stepAns++,同时更新右边界rightPos = maxPos = 4。

当 i 为 4 时,maxPos所能到达的最远下标maxPos = max(5,nums[4] + 4) = 8,当 i == rightPos时,表示 i 已经走到了一步能走到的最远处,此时需要走到下一个区域,因此步数stepAns++,同时更新右边界rightPos = maxPos = 8。 因此stepAns值为3, 即为走到数组尾的最少步数。

class Solution {
public:
    int jump(vector<int>& nums) {
        //maxPos当前所能到达的最远下标
        //rightPos右边界
        int maxPos = 0, rightPos = 0;
        int stepAns = 0;
        for(int i = 0;i < nums.size() - 1;i++){
            //更新当前所能到达的最远下标
            maxPos = max(maxPos,nums[i] + i);
            if(i == rightPos){
                rightPos = maxPos; //更新右边界
                stepAns++;
            }
        } 
        return stepAns;
    }
};
相关文章
|
4月前
|
算法
LeetCode第55题跳跃游戏
LeetCode第55题"跳跃游戏"的解题方法,通过记录当前最远可达到的位置并判断每个位置是否可达以及能否到达末尾,有效解决了跳跃至数组末尾的可行性问题。
LeetCode第55题跳跃游戏
|
2月前
Leetcode第55题(跳跃游戏)
LeetCode第55题“跳跃游戏”要求判断在一个非负整数数组中,从第一个位置出发,是否能够到达最后一个位置,其中每个位置的元素代表可跳跃的最大长度。
32 0
|
4月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
52 1
|
4月前
|
Python
【Leetcode刷题Python】174. 地下城游戏
LeetCode 174题 "地下城游戏" 的Python解决方案,使用动态规划算法计算骑士从左上角到右下角拯救公主所需的最低初始健康点数。
54 3
|
4月前
|
算法 索引 Python
【Leetcode刷题Python】55. 跳跃游戏
解决LeetCode "跳跃游戏"问题的Python实现代码,使用了贪心算法的思路。代码中初始化最远可到达位置 max_k,并遍历数组 nums,通过更新 max_k 来记录每次能跳到的最远位置,如果在任何时刻 max_k 大于或等于数组的最后一个索引,则返回 True,表示可以到达数组的末尾;如果当前索引 i 超出了 max_k,则返回 False,表示无法继续前进。时间复杂度为 O(n),空间复杂度为 O(1)。
50 1
|
4月前
|
算法
LeetCode第45题跳跃游戏 II
LeetCode第45题"跳跃游戏 II"的解题方法,通过一次循环和选择每个位置的最大可跳距离,有效减少了跳跃次数,简化了问题。
|
6月前
|
算法
力扣经典150题第三十八题:生命游戏
力扣经典150题第三十八题:生命游戏
44 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
58 6
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
120 2