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

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

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

#include <bits/stdc++.h>
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<<step<<endl;
        if(step >= len-1){
            return true;
        }
        return false;
    }
};

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

#include <bits/stdc++.h>
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<<step<<endl;
        if(step >= 1){
            return true;
        }
        return false;
    }
};
上一篇:实验3 转移指令跳转原理及其简单应用编程


下一篇:19条小技巧让你快速上手Ubuntu 11.04