leetcode解题: Jump Game (55)

发表于 | 分类于

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:

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

解法1： Greedy, O(N) Time

一个贪心的解法, 主要是维护一个variable叫reach, 他记录目前为止能达到的最远的距离. 然后扫描vector,如果当前的位置是不能达到的,则返回false.
否则更新reach的值,进入下一个元素.
C++

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

Java

1