LeetCode:45.跳跃游戏;55. 跳跃游戏

最新推荐文章于 2024-09-07 21:24:54 发布

Raven_csdn

最新推荐文章于 2024-09-07 21:24:54 发布

阅读量236

点赞数 1

分类专栏： LeetCode 文章标签： LeetCode 跳跃游戏

本文链接：https://blog.csdn.net/Raven_csdn/article/details/90266938

版权

LeetCode 专栏收录该内容

15 篇文章

订阅专栏

本文深入解析了两个跳跃游戏算法问题，一是寻找最少跳跃次数到达数组末尾，二是判断能否到达数组末尾。通过示例详细阐述了两种算法的实现过程，包括动态规划和贪心算法的应用。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

45.跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。

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

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

示例:

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

class Solution {
public:
    int jump(vector<int>& nums) {
        int n=nums.size();
        if(n<1){
            return n;
        }
        int index=1;
        vector<int> dp(n,0);
        for(int i=0;i<n;i++){
            if(index>=n) break;
            //向后更新，直到跳跃的最远位置,看从i这里能到达最远的地方
            while(index<n && nums[i]+i>=index){
                dp[index++]=dp[i]+1;
            }
        }
        return dp[n-1];
    }
};
当i=0的时候，index=1;
	index<n && nums[0]+0=2+0=2>=index;所以dp[1]=0+1=1
	       index=2;
	index<n && nums[0]+0=2>=index;所以dp[2]=dp[0]+1=1;
		   index=3;
    index<n 这个时候从0不能达到了，因为nums[0]+0=2<index=3;所以更新到index=3
当i=1的时候，index=3;
	index<n && nums[1]+1=3+1=4>=index=3;所以dp[3]=dp[1]+1=2;
	       index=4;
	index不小于n了所以不进入while循环
当i=2的时候，index=4==n;break;
    所以dp[n-1]结束了

55. 跳跃游戏

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

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

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ，所以你永远不可能到达最后一个位置。

方法一：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.size()==0){
            return false;
        }
        int step=0;//保存能跳的最远的地方
        for(int i=0;i<nums.size()-1;i++){
            if(i<=step){//如果i这里都达到不了，i之后的更到达不了，结束就OK了
                step=max(step,nums[i]+i);
            }else{
                break;
            }
        }
        return step>=((int)nums.size()-1);//是否能到大最后一步。
    }
};

方法二：

这个方法的思路是从后面往前走，例如3,2,1,0,4,从0到4需要一步即step=1,但是0<step，不能达到，所以他只能以后从前面的1到达，这个时候从1到4就需要2步了即step=2,即step++，那么什么step=1呢
[2,3,1,1,4] 从nums[3]=1到4,step=1,能够到达所以step=1,nums[2]需要1步就可以了。一次类推。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int step = 1;
        //3,2,1,0,4
        //0<step=1,step++,说明，我这一步到不了，接下来，你需要跨越两步。
        for(int i=nums.size()-2;i>=0;i--){
            if(nums[i] >= step){
                step = 1;
            }else{
                step ++;
            }
        }
    	return step == 1;
    }
};