LeetCode55. Jump Game

1、题目链接

https://leetcode.com/problems/jump-game/

2、解题思路

首先，这是一道比较经典的贪心算法题，何为贪心，我所理解的就是局部最优，不考虑全局的情况下（>_<说人话：就是说每次我都选最好的那一个），这道题就是说给你一个数组，数组里面的数代表你每次能跳跃的最大距离，就好比我走台阶，每一阶台阶上面都标了你最多只能往前走几个台阶，问你能不能从台阶的起点到达台阶的终点，那么，我们就走起来。我刚开始的想法是遍历数组并计算数组当前位置和当前数组的值（最多能走几步，贪心，我们就走最多的），看是否有大于等于数组长度的，如果有就输出true，没有就输出false，后来发现并不是这么简单，就比如[1, 0, 1, 0]这一组数据，我连第一个0都走不过去，还怎么往后走，于是乎就有了一个maxDistance这个值，这个值定义你当前能走得到的最远的距离，如果当前我遍历到的坐标比maxDistance大那么说明我遇到了0（不能走的）而且还走不过去，这时候也没必要往后遍历了；如果遍历到maxDistance已经可以走到最后一个位置的时候，这时候我们也没必要往后再遍历了，因为可以一步到位了，如果都不满足的话，那么我们就一直遍历然后更新maxDistance，遍历完成之后判断maxDistance是否可以走到最后一个位置

3、代码

• Java

private static boolean canJump(int[] nums) {
    if (null == nums || nums.length == 0) {
        return false;
    }
    if (nums.length == 1) {
        return true;
    }
    if (nums[0] == 0) {
        return false;
    }
    int maxDistance = 0;
    for (int i = 0; i < nums.length; i++) {
        if (maxDistance < i) {
            return false;
        } else if (maxDistance >= nums.length - 1) {
            return true;
        }
        maxDistance = Math.max(maxDistance, nums[i] + i);
    }
    return maxDistance >= nums.length - 1;
}

• Python

def canJump(numList):
    if numList is None or len(numList) == 0:
        return False
    if len(numList) == 1:
        return True
    if numList[0] == 0:
        return False
    maxDistance = 0
    for index in range(len(numList)):
        if maxDistance < index:
            return False
        elif maxDistance >= len(numList) - 1:
            return True
        maxDistance = max(maxDistance, numList[index] + index)
    return maxDistance >= len(numList) - 1

• JavaScript

var canJump = function(numList) {
    if (undefined === numList || null === numList || numList.length == 0) {
        return false
    }
    if (numList.length == 1) {
        return true
    }
    let maxDistance = 0
    for (let i = 0; i < numList.length; i++) {
        if (i > maxDistance) {
            return false
        } else if (maxDistance >= numList.length - 1) {
            return true
        }
        maxDistance = Math.max(maxDistance, numList[i] + i)
    }
    return maxDistance >= numList.length - 1
}

4、提交结果