每日一道算法之--跳跃游戏

动态规划回溯贪心

Word count: 728Reading time: 3 min

 2020/04/01   Share

跳跃游戏

力扣第55题 : https://leetcode-cn.com/problems/jump-game/

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

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

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

示例 1:

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

示例 2:

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

1. 回溯

使用回溯法,可以将所有的情况列举出来,如果有一种情况满足条件,则返回真

class Solution:
    tag = False

    def canJump(self, nums: List[int]) -> bool:
        if not nums:return False
        lenght = len(nums)
        def backtrack(step,nums):
            if step >= len(nums) - 1:
                # 如果有一个条件满足就返回真
                self.tag = True
                return True

            for i in range(1, step + 1):
                backtrack(nums[i], nums[i:])

        tag = backtrack(nums[0], nums)
        return True if self.tag else False

明显的,回溯方法没有剪枝,超出了时间限制

2. 动态规划

可以使用动态规划,去除回溯

class Solution:

    def canJump(self, nums: List[int]) -> bool:
        if len(nums) <= 1:
            return True
        dp = [0 for _ in range(len(nums) + 1)]
        dp[0] = nums[0]
        for pos in range(1, len(nums)):
            # 如果上一个索引的步数能够到达当前的索引位置
            if dp[pos - 1] >= pos:
                dp[pos] = max(dp[pos - 1], pos + nums[pos])
            # 上一个索引的步数不能够到达当前的索引位置,则证明肯定达到不了最后一个元素
            else:
                return False
            if dp[pos] >= len(nums) - 1:
                return True
        return False

3. 贪心算法

如果能到达某个位置，那一定能到达它前面的所有位置。

解法一:
初始化最远位置为0，然后遍历数组，如果当前位置能到达，并且当前位置+跳数>最远位置，就更新最远位置。最后比较最远位置和数组长度。

class Solution:

    def canJump(self, nums: List[int]) -> bool:
        max_i = 0       #初始化当前能到达最远的位置
        for i, jump in enumerate(nums):   #i为当前位置，jump是当前位置的跳数
            if max_i >= i and i+jump > max_i:  #如果当前位置能到达，并且当前位置+跳数>最远位置
                max_i = i+jump  #更新最远能到达位置
        return max_i>=i

解法二:
用current记录还能往前进多少格，每次进一current则为current-1和当前所处位置的值中的较大值。
当current为0时，代表无法前进，返回False。
反之则为True

class Solution:

    def canJump(self, nums: List[int]) -> bool:
        current=0
        for i in range(len(nums)-1):#最后一格不用检测
            current=max(current-1,nums[i])
            if current==0:return False
        return True

Author：liangweijiang

原文链接：https://liangweijiang.github.io/2020/04/01/algorithm-55/

发表日期：April 1st 2020, 3:30:30 pm

更新日期：April 1st 2020, 3:31:50 pm

Next Post

每日一道算法之--不同路径
Previous Post

数据结构学习笔记---跳表

CATALOG

1. 跳跃游戏

