跳跃游戏(一)

用一个变量记录能到达的最大下标，maxindex = i + nums[i].结束循环的时候判断该下标是否到达数组最后即可。

import java.util.*;
public class Solution {
    public boolean canJump (int[] nums) {
        int maxindex = 0;
        for(int i = 0; i < nums.length && i <= maxindex; ++i) {
            maxindex = Math.max(maxindex, i + nums[i]);
            if(maxindex >= nums.length - 1)return true;
        }
        return maxindex >= nums.length - 1;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return bool布尔型
     */
    public boolean canJump (int[] nums) {
        // write code here
        //最大跳远距离
        int maxReach=0;
        //循环维护最大跳转距离
        for(int i=0;i<nums.length;i++){
            //如果最大跳远距离无法到达该点为false
            if(maxReach<i){
                return false;
            }
            //如果最大跳远距离大等于目标位置为true
            if(maxReach>=nums.length-1){
                return true;
            }
            //遍历每个节点，只要该节点的跳远距离大于maxReach，就更新maxReach
            maxReach=Math.max(maxReach,i+nums[i]);
        }

        return true;
    }
}

package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return bool布尔型
*/
func canJump( nums []int ) bool {
    n:=len(nums)
    end:=0
    for i:=0;i<n;i++{
        if end<i{
            return false
        }
        end=max(end,i+nums[i])
    }
    return true
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

public boolean canJump (int[] nums) {
		// write code here
		int len = nums.length;
		int end = 0;
		for (int i = 0; i < len; i++) {
			if (i > end) return false;
			end = Math.max(end,i + nums[i]);
		}
		return true;
	}

 public boolean canJump (int[] nums) {
        // write code here
        if(nums.length==1)
            return true;
        int num=1;
        int j=1;
        for(int i=nums.length-1;i>0;){
            if(i-j<0)
                return false;
            if(nums[i-j]>=j){
                 if(i-j==0)
                    return true;
                i--;
                j=1;
            }else{
                j++;
            }
        }
        return false;
    }
}

class Solution:
    def canJump(self , nums: List[int]) -> bool:
        # write code here
        reach = nums[0]
        for i in range(len(nums)):
            if reach < i: 
                return False
            if i + nums[i]>= len(nums)-1:
                return True
            reach = max(reach,i + nums[i])

    //贪心策略：在cover范围内移动，不断更新cover范围，若可以覆盖整个范围，那么最后点可达
    //直白说，就是每次取最大覆盖范围，最后就可以取到全局最大范围
    bool canJump(vector<int>& nums) {
        // write code here
        int cover=0;//在没跳的时候，只能从下标为0的地方开始跳，就覆盖范围为0
        for(int i=0;i<=cover;i++)
        {
            cover=max(cover,i+nums[i]);
            if(cover>=nums.size()-1) 
                return true;
        }
        return false;
    }

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int res=0;
        for(int i=0;i<nums.size();i++)
        {
            if(i>res)return false;
            res=max(res,nums[i]+i);
            if(res>=nums.size()-1)return true;
        }
        return false;
    }
};

public static boolean canJump(int[] nums) {
        int res=0;
        for (int i = 0; i < nums.length; i++) {
            //严格控制0的输出
            if(i>res) return false;
            res=Math.max(res,i+nums[i]);
            if(res>=nums.length-1) return true;
        }
        return false;
    }