LeetCode_55 跳跃游戏.md · ZechariahZheng/blog文档 - Gitee.com

9月25日晚8点，Gitee 吐槽大会正式开幕，吐槽火力全开，Gitee 接招不慌！

加入 Gitee

与超过 1200万开发者一起发现、参与优秀开源项目，私有仓库也完全免费：）

该仓库未声明开源许可证文件（LICENSE），使用请关注具体项目描述及其代码上游依赖。

克隆/下载

LeetCode_55 跳跃游戏.md 1.35 KB

一键复制编辑原始数据按行查看历史

提交于 2019-12-04 09:53 . LeetCode_55

## LeetCode_55 跳跃游戏

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

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

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

示例 1:

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

**思路：如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点。可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新。如果可以一直跳到最后，就成功了。**

```java
class Solution {
    public boolean canJump(int[] nums) {
        int max = 0;
        for (int i = 0; i < nums.length-1; i++) {
            if (i > max)
                return false;
            //能跳的最远距离
            max = Math.max(max, i+nums[i]);
        }
        return max>=nums.length-1 ? true : false;
    }
}
```

宽度搜索超时

```java
宽度搜索
class Solution {
    public boolean canJump(int[] nums) {
        dfs(nums, 0);
    }
	private boolean dfs(int[] nums, int index) {
		if (index == nums.length-1)
			return true;

		for (int i = 1; i < nums[index]; i++) {
			if (dfs(nums, index+i))
				return true;
		}
		return false;
	}
}
```

马建仓 AI 助手

尝试更多

代码解读

代码找茬

代码优化

1

https://gitee.com/ZechariahZheng/blog_document.git

git@gitee.com:ZechariahZheng/blog_document.git

ZechariahZheng

blog_document

blog文档

master