Algorithm

[LeetCode 55] Jump Game [Java]

顿搜

2018-01-27

0 评论

773 阅读

正在检测是否收录...

01/27

1. Description

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.

2. Example

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

3. Code

public class LeetCode0055 {
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }

        int longestSkip = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            if (i > longestSkip) {
                return false;
            }
            if (i + nums[i] > longestSkip) {
                longestSkip = i + nums[i];
            }
            if (longestSkip >= nums.length - 1) {
                return true;
            }
        }
        return longestSkip >= nums.length - 1;
    }

    public static void main(String[] args) {
        LeetCode0055 leetcode = new LeetCode0055();
        System.out.println(leetcode.canJump(new int[] { 3, 0, 8, 2, 0, 0, 1 }));
    }
}

Greedy

朗读