LeetCode -- Jump Game

LeetCode -- Jump Game

題目描述：


Given an array of non-negative integers, you are initially positioned at the first index of the array.


Each element in the array represents your maximum jump length at that position.


Determine if you are able to reach the last index.


For example:
A = [2,3,1,1,4], return true.


A = [3,2,1,0,4], return false.


思路：


就是給定一個數組，每個數字(nums[i]=n)表示當前索引i所能到達的最遠索引為i + nums[i]。
例如，對於[3,2,1,0,4]來說，前三位所能到達的最遠索引為：0+3,1+2,2+1均為3，可nums[3]為，故無法繼續前行。


問，判斷從索引0開始出發，能否到達末尾。


1. 使用1個reachableIndex來表示所能到達的最遠索引，初始化為nums[0]+0 = nums[0]，如果第一個索引為0，直接返回false
2. 從nums[1]開始往後走，如果reachableIndex小於當前索引，而當前nums[i]又為0，返回false
3. 如果num[i]+i的值比當前的reachableIndex大，更新reachableIndex
4. 如果reachableIndex比nums的長度大，返回True








實現代碼：

public class Solution {
    public bool CanJump(int[] nums) 
    {
    	if(nums.Length <= 1){
    		return true;
    	}
    	
    	var reachableIndex = nums[0]; // nums[0] + 0
    	if(reachableIndex == 0){
    		return false;
    	}
	
    	for(var i = 1;i < nums.Length; i++){
    		if(reachableIndex <= i && nums[i] == 0){
    			return false;
    		}
    		
    		if(nums[i] + i > reachableIndex){
    			reachableIndex = nums[i] + i;
    		}
    		
    		if(reachableIndex >= nums.Length - 1){
    			return true;
    		}
    	}
    	
    	return false;
    }


}