leetcode55 -- Jump Game (被面过)

leetcode55 -- Jump Game (被面过)

题目

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.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

这个题目比较好理解,意思就是问能不能跳过来,上面的数代表的是青蛙能跳的最多的步数,并不是说非得跳那么多.

解法1

第一次见这个题的时候觉得像是动态规划,因为能够跳到第n个位置,一定是从前面的某个位置跳过来的,而且能跳到第n个位置,那么前面n-1个位置也一定能够跳到.所以最初就是想的DP的思路来解这个问题.


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        array = [0] + [False]*len(nums)  # 第一个0是为了方便实现.
        # array[i]  i>=1 代表着能够跳到当前的位置.
        
        # 先初始化为全部都能够跳过去,至少第一个位置肯定是可以的,因为不用跳
        array[1] = True
        for i in range(2, len(nums)+1):
            # 能够跳到当前位置,一定是从之前的某个位置跳过来的.
            for j in range(1,i):
                if array[j] and nums[j-1]+(j-1)>=i-1:  # 意思是之前的那个位置可以跳并且可以跳到i
                    array[i] = True
                    break

        return array[-1]

不过这样有些超时了.

解法2

其实想一想这个问的其实并没有那么难,问的只是能不能跳到头,那说明只要能够从某一个位置能够跳过来的话,那就可以了.

比如说从第一个位置开始跳的时候,可以最多跳到index为2的位置,相当于跳的范围可以到达Index为2,然后第二次从index为1的位置开始跳,再看它能跳的最大的位置,这样思路就出来了。

可以用两个指标,一个指标代表起跳的位置,记为i, 另外一个指标j代表当前所有可能中能跳到的最大的范围.然后每一次都不断地更新j和i,注意i更新的前提是不超过j.

代码如下


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        j = 0
        i = 0
        while i< len(nums):
            # update j
            j = max(j,i+nums[i])   # 最大范围.
            if j>= len(nums)-1:
                return True
            if i<j:
                i += 1   # 从下一下跳.
            else:        # 意味着不能够再往下跳.
                return False

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦