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;
    }
};
相关文章
|
5月前
|
算法 Go 索引
【LeetCode 热题100】45:跳跃游戏 II(详细解析)(Go语言版)
本文详细解析了力扣第45题“跳跃游戏II”的三种解法:贪心算法、动态规划和反向贪心。贪心算法通过选择每一步能跳到的最远位置,实现O(n)时间复杂度与O(1)空间复杂度,是面试首选;动态规划以自底向上的方式构建状态转移方程,适合初学者理解但效率较低;反向贪心从终点逆向寻找最优跳点,逻辑清晰但性能欠佳。文章对比了各方法的优劣,并提供了Go语言代码实现,助你掌握最小跳跃次数问题的核心技巧。
195 15
|
5月前
|
算法 Go
【LeetCode 热题100】55:跳跃游戏(详细解析)(Go语言版)
本篇解析详细讲解了 LeetCode 热题 55——跳跃游戏(Jump Game)。通过判断是否能从数组起点跳至终点,介绍了两种高效解法:贪心算法和反向思维。贪心法通过维护最远可达位置 `maxReach` 实现一次遍历,时间复杂度 O(n),空间复杂度 O(1);反向法则从终点回溯,判断是否可到达起点。两者均简洁高效,适合面试使用。延伸题目如 LeetCode 45 进一步提升挑战。
145 7
LeetCode第55题跳跃游戏
LeetCode第55题"跳跃游戏"的解题方法,通过记录当前最远可达到的位置并判断每个位置是否可达以及能否到达末尾,有效解决了跳跃至数组末尾的可行性问题。
LeetCode第55题跳跃游戏
|
11月前
Leetcode第55题(跳跃游戏)
LeetCode第55题“跳跃游戏”要求判断在一个非负整数数组中,从第一个位置出发,是否能够到达最后一个位置,其中每个位置的元素代表可跳跃的最大长度。
74 0
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
135 1
LeetCode第45题跳跃游戏 II
LeetCode第45题"跳跃游戏 II"的解题方法,通过一次循环和选择每个位置的最大可跳距离,有效减少了跳跃次数,简化了问题。
|
12月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
169 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
130 6
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
282 2
|
12月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
170 3
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口