跳跃游戏 Jump Game

原创
2017/09/05 16:49
阅读数 15

问题:

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.

解决:

【注】给定一个数组,从第一个元素开始,元素的值表示能够往后跳的最大距离,问这样一个数组能否跳到最后一个元素。

① 使用动态规划的思路。正向思路。注意题目中A[i]表示的是在位置i,“最大”的跳跃距离,而并不是指在位置i只能跳A[i]的距离。所以当跳到位置i后,能达到的最大的距离至少是i+A[i]。根据贪心算法的思路,记录一个当前能达到的最远距离reach。

class Solution { //9ms
    public boolean canJump(int[] nums) {
        int reach = 0;
        for(int i = 0;i < nums.length;i ++){
            if(i > reach) return false;
            reach = Math.max(nums[i] + i,reach);

        }
        return true;
    }
}

② 反向思路。

class Solution { //7ms
    public boolean canJump(int[] nums) {
        int n = nums.length - 1;
        int reach = n;
        for(int i = n; i >= 0; i--){
            if(i + nums[i] >= reach)
                reach = i;
        }
        return reach == 0;
    }
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部