55. 跳跃游戏

#55. 跳跃游戏

2020/4/17每日一题打卡 难度：中等

题目描述

解题思路

1、贪心思想

public boolean canJump(int[] nums) {       
	int n = nums.length;         
	if(n <= 1)             
		return true;         
	int max = nums[0];  //记录当前可以到达的最远长度         
	for (int i = 1; i < n - 1; i++) {             
		if (max >= i) {  //如果当前位置能到达，如果nums[i]小于max则说明当前位置都不能到                 
			max = Math.max(max, i + nums[i]);            
		}             
		else {                
			return false;            
		}            
		if(max >= n-1)   //如果已经能到达最后，返回,减少比较次数                
			return true;        
		}
	}         
	return max >= n - 1;    
}

2、从后往前遍历

看执行时间1ms的大佬的方法，从后面往前遍历，更新能到达的位置，如果最后等于0则说明可以从起点到终点。大佬实在是太强了

public boolean canJump(int[] nums) {        
	int last = nums.length - 1;  //最后能到达的下标         
	for (int i = nums.length - 1; i >= 0; i--) {            
		if(i+nums[i] >= last) { //如果能到达                
			last = i;            
		}         
	}         
	return last == 0;  //last = 0则表示能到从第一个到最后一个    
}

3、只关注0的位置

还有一种思路就是，如果全部数组都不等于0，那么肯定满足要求。如果遇到0，那么就往前搜寻有没有位置能跳过这个0。

public static boolean canJump2(int[] nums) {
   	if(nums.length <= 1)
             return true;
   	for (int i = 0; i < nums.length - 1; i++) {
	   	if(0 == nums[i]) {
	    		int j = i;
	    		for (; j >= 0; j--) {
	     			if(nums[j] + j > i) {
	      				j = -2;//标记找到
	      				break;
	     			}
	    		}
	    		if(j != -2) return false;
	   	}
	   }	
	return true;  
     }