LeetCode 55跳跃游戏.md

LeetCode 55跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4] 输出: false 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

分析 这题我们可以使用一个O(n)的方法，和前面一些题的方法也很相似，遍历这个数组，遍历的同时用一个index标记最大值。如果可以更新最大值那么就更新，如果index比最大值还大，那就直接返回false。

可到达的：

不可到达的：

具体ac代码：

public boolean canJump(int[] nums) {
     boolean jud[]=new boolean[nums.length];
	 int maxlen=nums[0];
	 int index=0;
	 while (index<nums.length) {
		if(index>maxlen)
			return false;
		if(index+nums[index]>maxlen)
		{
			maxlen=index+nums[index];
		}
		else {
			index++;
		}
	}
	 return true;
   }

结语

原创不易，bigsai请你帮两件事帮忙一下:

1. star支持一下， 您的肯定是我在平台创作的源源动力。

2. 微信搜索「bigsai」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。

记得关注、咱们下次再见！