【Day 67 】2023-08-15 - 55. 跳跃游戏

[azl397985856]

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 ， 所以你永远不可能到达最后一个位置。

[GuitarYs]

class JumpGame:
    def canJump(self, nums):
        position = 0
        for i in range(len(nums)):
            if position >= len(nums) - 1:
                return True
            if nums[position] == 0:
                return False
            max_jump = nums[position]
            position = position + max_jump
        return False

[freesan44]

class Solution {
    func canJump(_ nums: [Int]) -> Bool {
        var maxIndex = 0
        let length = nums.count

        for i in 0..<(length - 1) {
            if maxIndex < i {
                return false
            }
            maxIndex = max(maxIndex, nums[i] + i)

            if maxIndex >= length - 1 {
                return true
            }
        }

        return maxIndex >= length - 1

    }
}

[Diana21170648]

思路

具体就是用一个变量记录当前能够到达的最大的索引

代码

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        m_max=0
        n=len(nums)
        for i in range(n-1):
            if m_max<i:
                return Fslse
            m_max=max(m_max,nums[i]+i)
            if m_max>=n-1:
                return True
        return m_max>=n-1

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[Beanza]

class Solution: def canJump(self, nums: List[int]) -> bool: m_max=0 n=len(nums) for i in range(n-1): if m_max<i: return Fslse m_max=max(m_max,nums[i]+i) if m_max>=n-1: return True return m_max>=n-1

[Fuku-L]

代码

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int maxPosition = 0;
        for (int i = 0; i < n && maxPosition < n - 1; i++) {
            if (maxPosition < i) {
                return false;
            }
            maxPosition = Math.max(maxPosition, i + nums[i]);
        }
        return true;
    }
}

[Alexno1no2]

# 初始化最远位置为0，然后遍历队列，如果当前位置能到达，并且当前位置+跳数>最远位置，就更新最远位置。最后比较最远位置和队列长度。
class Solution:
    def canJump(self, nums) :
        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

[Momogir]

#第0个位置能跳到的最大长度是否 >= n
# => 第n-1个位置能跳的最大长度
# => 第n-2个位置能跳的最大长度
#...
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n=len(nums)
        if n==1 : return True

        dp=[0]*n
        for i in range(n)[::-1]:
            if i==n-1:
                dp[i]=nums[i]
            else:
                dp[i]=max(1+dp[i+1],nums[i]) if nums[i]>0 else 0
            # print(i,dp[i])
        print(dp)
        return dp[0]>=n-1