leetcode-55-Jump-Game

发表于   |  

描述

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.

Example 1:

1
2
3
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

1
2
3
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

分析

贪心算法，每次跳都保证剩下的步数最大。f(n) 表示到 n 索引下还剩的步数，则有 $f(i) = max(f(i-1), A[i-1]) - 1$，i > 1，f(0) = 0。如果出现了小于零的情况，则表示不能跳过去。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean canJump(int[] nums) {
        int[] f = new int[nums.length];
        for (int i = 1; i < nums.length; i++) {
            f[i] = Math.max(f[i-1], nums[i-1]) - 1;
            if (f[i] < 0) {
                return false;
            }
        }
        // return f[nums.length-1] >= 0;
        return true;
    }
}

解决方案2（Golang）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func canJump(nums []int) bool {
    numsLen := len(nums)
    dp := make([]int, numsLen)
    dp[0] = 0
    for i := 1; i < len(nums); i++ {
        if dp[i-1] > nums[i-1] {
            dp[i] = dp[i-1] - 1;
        } else {
            dp[i] = nums[i-1] - 1;
        }
        if dp[i] < 0 {
            return false
        }
    }
    return true
}

相关问题

题目来源