【LeetCode-55】55.跳躍遊戲

55.跳躍遊戲

給定一個非負整數數組，你最初位于數組的第一個位置。

數組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達最後一個位置。

貪心法

參考思路

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        if(n <= 1) {
            return true;
        }
        // 設定目前可以到達的最大坐标
        int farthest = nums[0];
        for(int i = 0; i < n; i++) {
            // 表示目前坐标可以達到
            if(i <= farthest) {
                // 更新可以達到的最遠坐标
                farthest = Math.max(farthest, i + nums[i]);
            } else {
                break;
            }
        }
        return farthest >= n - 1 ? true : false;
    }
}
           

進階題

45. 跳躍遊戲 II