【LeetCode】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.

For example:

A = 

[2,3,1,1,4]

, return 

true

.

A = 

[3,2,1,0,4]

, return 

false

.

【解析】

題意：給定一個數組，從第一個元素開始，元素的值表示能夠往後跳的最大距離，問這樣一個數組能否跳到最後一個元素。

思路：貪心。

這好像是第一次寫貪心，代碼不是很好，是以下面隻讨論兩個網上比較簡潔的代碼。

【逆向思路】

來源：https://oj.leetcode.com/discuss/11422/simplest-o-n-solution-with-constant-space

public class Solution {
    public boolean canJump(int[] A) {
        int last = A.length - 1;
        for (int i = A.length - 2; i >= 0; i--) {
            if (i + A[i] >= last) {
                last = i;
            }
        }
        return (last <= 0);
    }
}
           

【正向思路】

來源：https://oj.leetcode.com/discuss/15567/linear-and-simple-solution-in-c

public class Solution {
    public boolean canJump(int[] A) {
        int reach = 0;
        int i = 0;
        for ( ; i < A.length && i <= reach; i++) {
            reach = Math.max(reach, i + A[i]);
        }
        return (i == A.length);
    }
}
           

個人比較傾向于第二種解法，畢竟是正向思維。另外，Jump Game II 利用該思路也比較容易延伸，參見 【LeetCode】Jump Game II 解題報告。