力扣【动态规划】-基础题-跳跃游戏

1001-高同学

发表文章数:265

首页 » 算法 » 正文

题目链接:https://leetcode-cn.com/problems/jump-game/
这道题有两种解题思路,一种是官方给出的解答方案 通过整个数组能够跳跃的最大距离进行判断,另一种是我个人的解答方案 根据下一步能够跳跃的最大距离。

方案一:
按照官方解题思路,只需要在最后一个数之前找到大于等于整个数组长度的数即可。
代码:

#include 
using namespace std;

class Solution {
public:
    bool canJump(vector<int>& nums) {
        
        int len = nums.size();
        if(len == 1){
            return true;
        }
        if(nums[0] == 0 && len > 1){
            return false;
        }
        //step为可以走的最远距离
        int step = nums[0];
        for(int i=1; i<len-1; i++){
            if(step>=i){
                step = max(step, nums[i]+i);
            }
        }
        // cout<
        if(step >= len-1){
            return true;
        }
        return false;
    }
};

方案二:只以当前可以走的步数为基准,当最后一步可以走的步数>=1时即为成功。
此方法需要注意:如果在走的过程中某一步可以走的步数为0时,说明无法到达下一步,此时即可判断为false

#include 
using namespace std;

class Solution {
public:
    bool canJump(vector<int>& nums) {
        
        int len = nums.size();
        if(len == 1){
            return true;
        }
        if(nums[0] == 0 && len > 1){
            return false;
        }
        //step为可以走的最大步数
        int step = nums[0];
        for(int i=1; i<len-1; i++){
            if((step-1)>nums[i]){
                step = step-1;
            }else{
                step = nums[i];
            }
            if(step == 0){
                return false;
            }
        }
        // cout<
        if(step >= 1){
            return true;
        }
        return false;
    }
};

拜师教育学员文章:作者:1001-高同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《力扣【动态规划】-基础题-跳跃游戏》 发布于2022-01-20

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录