leetcode 55. 跳跃游戏

一、题意

给定一个非负整数数组 nums ，你最初位于数组的第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

二、解法

贪心算法。
解法1：
计算出 i + n u m s [ i ] i+nums[i] i+nums[i]或目前最大值是否能到下个位置，如果能，则继续，不能则返回false。
解法2(官方)：
计算出能到达最右的位置rightmost，如果当前坐标 ≤ \leq ≤rightmost， r i g h t m o s t = m a x ( r i g h t m o s t , n u m s [ i ] + i ) rightmost=max(rightmost,nums[i]+i) rightmost=max(rightmost,nums[i]+i), 判断rightmost是否大于最大数值下标，若是，则返回true。

三、代码

解法一：

bool canJump(vector<int>& nums) {
            int maxN = 0;
            int n = nums.size()-1;
            for(int i=0;i<nums.size()-1;i++){
                int s = nums[i]+i;
                    if(s<i+1&&maxN<i+1){
                        return false;
                    }
                    maxN= max(s,maxN);
            }
            return true;
    }

解法二：

 bool canJump(vector<int>& nums) {
            int maxN = 0;
            int n = nums.size();
            for(int i=0;i<nums.size();i++){
                    if(i<=maxN){
                        int s = nums[i]+i;
                        maxN = max(s,maxN);
                        if(maxN>=n-1) return true;
                    }
            }
            return false;
    }

四、引用

[1] leetcode：55. 跳跃游戏
[2] leetcode：跳跃游戏官方解法