Leetcode 55.跳跃游戏

Posted on |

55. 跳跃游戏

题目

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

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

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

1
2
3
4
5
6
7
8
9
10
示例 1:

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

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

方法

方法1

每次迭代可以跳跃的步数范围是$[1,nums[i]+1)$。不能到达最后位置的两种情况：

  • 足够多的步数，但是越过最后位置。由于题目设置中仅限定每个位置最大跳跃长度，如果跳少几步仍然可以到达终点，所以排除这种情况
  • 没有足够的步数reach，使其跳到最后位置。
    因此，本题目只需要考察第二种情况即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        reach = 0
        for idx in range(len(nums)):
            # print(idx,reach)
            # 如果当前位置idx超出所能到达的最远位置，不合理，直接False，推出循环
            if idx > reach:
                break
            # 更新下一次迭代能到达的最远位置
            reach = max(nums[idx]+idx,reach)
        return reach >= len(nums)-1

reach表示每次迭代能够达到的最远的位置，如果reach大于等于数组的长度，则表示可以到达数组最后的位置

  • 如果reach>len(nums)-1,则表示能够跳到最后位置
  • 否则，在同一位置上reach将保持静止，直到它被迭代器“追逐”（idx）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution(object):
        def canJump(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """

            idx,reach,length=0,0,len(nums)
            while idx<=reach and idx<length:
                reach=max(reach,idx+nums[idx])
                idx+=1
            return reach>=length-1

方法2：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        dp=[False]*len(nums)
        dp[0]=True

        for i in range(1,len(nums)):
            for j in range(i-1,-1,-1):
                if dp[j]==True and j+nums[j]>=i:
                    dp[i]=True
                    break
        return dp[-1]x

参考资料