55-跳跃游戏

Leetcode题解
  1. 55、跳跃游戏
    1. 题目：
    2. 题解：

55、跳跃游戏

https://leetcode-cn.com/problems/jump-game/

题目：

amr5qA.png

题解：

给大佬跪了，如此简洁的解法！

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

作者：ikaruga
链接：https://leetcode-cn.com/problems/jump-game/solution/55-by-ikaruga/

此题解法总结起来就两个判断：

1、判断当前位置是否可达（也就是比较之前获得的最远可达位置是否大于当前位置），如果不可达说明已经走到头了，失败！

2、判断当前位置可达的最远位置是否大于上个位置获得的可达最远位置（刷新当前最远可达位置），如果大于那就说明我们的可达最远位置该更新了！

最后，顺利的走到了终点，跳出循环，奥力给。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int max_location = 0;
        for (int cur_location = 0; cur_location < nums.size(); cur_location++) {
            if (cur_location > max_location) {
                return false;
            }
            max_location = max(max_location, cur_location + nums[cur_location]);
        }
        return true;
    }
};

当前网速较慢或者你使用的浏览器不支持博客特定功能，请尝试刷新或换用Chrome、Firefox等现代浏览器