欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

55.跳跃游戏

程序员文章站 2024-03-15 09:04:23
...

中等

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/jump-game
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


解法1:top to bottom的动态规划:

用一个表,存储每个位置的通路情况,初始状态都是未知的状态0,只有终点位置是1.

有一种递归的思想。

首先jump(0)检查位置0的点,它可以去到位置1,2,3.我们依次检查三个子节点。

    检查位置1,jump(1).它可以去到位置2.

         检查位置2,jump(2).遍历完后发现,没有通路,更新位置2的通路状态=-1,返回false到jump(1).

    位置1遍历结束,jump(1)完成,没有通路,更新位置1的通路状态=-1,返回false到jump(0).

jump(0)继续遍历jump(2),因为2的通路状态是-1,所以返回false到jump(0).

jump(0)继续遍历jump(3).位置3可以去到位置4或者位置5,位置5越界所以排除。

    jump(3)遍历jump(4),jump(4)的通路状态为1,所以返回true.到jump(3).

jump(3)返回true到jump(0).

jump(0)再返回true.

此时说明从0点可以找到通路到最后。

55.跳跃游戏

代码实现

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    const totalLength = nums.length
    const memo = Array(totalLength).fill(0)  //记录每个点的通路状态
    memo[totalLength-1] = 1                //终点必然是通的
    
    function jump(position) {
        if(memo[position] === 1) {
            return true
        }else if(memo[position] === -1) {
            return false
        }

        //从当前点最多可以跳到哪个位置,不能越界
        const maxJump = Math.min(position + nums[position], totalLength-1) 
        
        for (let i = position+1; i <= maxJump; i++) {
            let jumpResult = jump(i)
            if (jumpResult === true) {
                memo[position] = 1     //这里是position哦,因为子路通了
                return true
            }
        }
        //遍历所有可能的通路都没发现,更新位置i通路状态,返回false.
        memo[position] = -1
        return false
    }

    let result = jump(0)
    return result

};

解法2:

从后向前找。

将最后一个位置通路状态标位1,其他位置都为0。

从倒数第二个位置开始,依次向前找。

  位置3,可以到达位置4,状态更新为1。

  位置2,到不了3或者4,状态更新为-1。

  位置1,到不了3或者4,状态更新为-1。

  位置0,可以到3,状态更新为1.

返回位置0的道路状态值。

55.跳跃游戏

代码实现

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    const totalLength = nums.length
    const memo = Array(totalLength).fill(0)
    memo[totalLength-1] = 1

    for(let position = totalLength-2; position >= 0; position--){  //从倒数第二位开始检查
        let maxJump = Math.min(position + nums[position], totalLength-1)
        for (let j = position+1; j <= maxJump; j++) { //检查可以到的点,有没有通的
            if (memo[j] === 1) {
                memo[position] = 1   //找到1个,修改当前点状态
                break
            }
        }
    }

    if(memo[0] === 1) {
        return true
    }else {
        return false
    }
};

贪心算法 

就和上面一个思路很像,不过是用一个变量存储当前可行的节点

从倒数第二位置开始遍历

  位置3+步长>maxJump,可以跳到最后一个位置,这是个优位置,将maxJump更新为位置3

  位置2,不能跳到maxJump,看下一个

  位置1,不能跳到maxJump,看下一个

  位置0+步长 >= maxJump, 可以跳到maxJump,更新maxJump = 0

返回maxJump是否等于0,等于0则是存在通路的

55.跳跃游戏

代码实现

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    const totalLength = nums.length
    let maxJump = totalLength - 1           //初始值设为最后一个位置

    for(let i = totalLength-2; i>=0; i--) {

        if(i+nums[i] >= maxJump) {          //能不能跳过一个优位置
            maxJump = i                     //将现在位置标为一个优位置
        }
    }

    // if (maxJump === 0) {
    //     return true
    // }else {
    //     return false
    // }

    return maxJump === 0    //这样写更简洁
};

最快的是贪心,其次是bottom2top,最慢的是top2bottom,因为有递归

55.跳跃游戏

 

相关标签: leetcode