【Day 67 】2023-04-21 - 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 ， 所以你永远不可能到达最后一个位置。

[joemonkeylee]

思路

如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点 可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新 如果可以一直跳到最后，就成功了

代码

     public bool CanJump(int[] nums)
        {
            int k = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                if (i > k) return false;
                k = Math.Max(k, i + nums[i]);
            }
            return true;
        }

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[lp1506947671]

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        """思路同上"""
        _max = 0
        _len = len(nums)
        for i in range(_len-1):
            if _max < i:
                return False
            _max = max(_max, nums[i] + i)
            # 下面这个判断可有可无，但提交的时候数据会好看点
            if _max >= _len - 1:
                return True
        return _max >= _len - 1

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)

[kofzhang]

思路

记录当前能到达的最大位置，遍历列表，如果当前位置大于记录的最大位置，说明到不了。

复杂度

时间复杂度：O(n) 空间复杂度：O(1)

代码

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        pos = 0
        for index,n in enumerate(nums):
            if pos<index:
                return False
            if index+n>pos:
                pos = index+n
        return True

[RestlessBreeze]

code

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int k = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (i > k)
                return false;
            k = max(k, i + nums[i]);
        }
        return true;
    }
};

[LIMBO42]

class Solution {
public:
    bool canJump(vector<int>& nums) {
        // if(nums.size() == 1) return true;
        // // vector<bool>(nums.size(), false) dp;
        // vector<bool> dp(nums.size(), false);
        // dp[nums.size()-1] = true;
        // for(int i = nums.size()-2; i >= 0; --i) {
        //     for(int j = 1; j <= nums[i] && i + j < nums.size(); ++j) {
        //         if(dp[i+j]) {
        //             dp[i] = true;
        //             break;
        //         }
        //     }
        // }
        // return dp[0];
        int energy = nums[0];
        for(int i = 1; i < nums.size(); ++i) {
            // 当走到energy更大的时候，直接选那个节点
            energy--;
            if(energy < 0) return false;
            energy = max(energy, nums[i]);
        }
        return true;
    }
};

[Zoeyzyzyzy]

class Solution {
    // 想象每次跳跃能覆盖到的最大范围为多少，若覆盖最大范围的大小超过array length则说明可以到达last index,
    // 若到最后也没能覆盖到last index，则说明不能跳过去
    public boolean canJump(int[] nums) {
        int range = 0;
        for (int i = 0; i <= range; i++) {
            range = Math.max(range, i + nums[i]);
            if (range >= nums.length - 1)
                return true;
        }
        return false;
    }
}

[NorthSeacoder]

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    let cover = 0;
    if (nums.length === 1) return true;
    for (let i = 0; i <= cover; i++) {
        cover = Math.max(i + nums[i], cover);
        if (cover >= nums.length - 1) return true;
    }
    return false;
};

[Meisgithub]

public:
    bool canJump(vector<int>& nums) {
        int maxPos = 0;
        int n = nums.size();
        int i = 0;
        while (i < n - 1)
        {
            int next = i;
            for (int j = i; j <= nums[i] + i; j++)
            {
                if (j + nums[j] > maxPos)
                {
                    maxPos = j + nums[j];
                    next = j;
                    if (maxPos >= n - 1)
                    {
                        return true;
                    }
                }
            }
            if (next == i)
            {
                return false;
            }
            i = next;
        }
        return true;
    }
};

[Diana21170648]

思路

贪心，只需要记录和更新所能达到的最大索引，能到达某个位置，证明左边的位置都能到达，尝试怎么样能走的最远，并考虑到达最后位置或者超过最后位置都为真的情况

from typing import List
class Solution:
    def jumpgames(self,A:List[int])->bool:
        _max=0
        n=len(A)
        for i in range (n):
            if _max<i:
                return False
            _max=max(_max,A[i]+i)
            if _max>=i:
                return True
        return _max>=n-1#return 和for对齐，不能和def对齐
Solution().jumpgames([2,3,1,1,4])

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

[aoxiangw]

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

time, space: O(n), O(1)

[chanceyliu]

思路

贪心

代码

function canJump(nums: number[]): boolean {
  let rightmost = 0;
  for (let i = 0; i < nums.length; i++) {
    if (rightmost >= nums.length - 1) {
      return true;
    }
    if (i > rightmost) {
      return false;
    }
    rightmost = Math.max(rightmost, i + nums[i]);
  }
  return false;
}

[tzuikuo]

思路

贪心，循环数组，记录跳最远的距离，不超过最远距离

代码

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxright=0,n=nums.size();
        for(int i=0;i<n;i++){
            if(i>maxright) break;
            maxright=max(maxright,i+nums[i]);
        }
        if(maxright>=n-1) return true;
        return false;
    }
};

复杂度分析 -时间O(n) -空间O(1)

[FireHaoSky]

思路：贪心算法

代码：python

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

复杂度分析：

"""
时间复杂度：O(n)
空间复杂度：O(1)
"""

[Abby-xu]

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        max_pos = 0
        i = 0
        while i <= max_pos:
            max_pos = max(max_pos, i + nums[i])
            if max_pos >= n-1: return True
            i += 1
        return False

[snmyj]

public:
    bool canJump(vector<int>& nums) {
        if(nums.size()==1) return true;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==0){
                int cnt=0;
                for(int j=0;j<i;j++){
                   if((nums[j]<=i-j)&&i!=nums.size()-1) cnt++;
                }
                if(cnt==i) return false;
            }
        }
        return true;
    }
};

[sye9286]

代码

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    let end = nums.length - 1;

    for (let i = nums.length - 2; i >= 0; i--) {
        if (end - i <= nums[i]) {
            end = i;
        }
    }

    return end == 0;
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)

[linlizzz]

class Solution:
    def canJump(self, nums: List[int]) -> bool:

        _max = 0
        _len = len(nums)
        for i in range(_len-1):
            if _max < i:
                return False
            _max = max(_max, nums[i] + i)

            if _max >= _len - 1:
                return True
        return _max >= _len - 1

T(n) = O(n)

S(n) = O(1)

[harperz24]

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

[chocolate-emperor]

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int l = nums.size();
        int i = 0;
        if(nums.size()<=1)  return true;

        while(i<l){
            int maxStep = 0,curr = i;
            if(nums[i]==0)  return false;

            for(int j = i+1;j<=nums[i]+i && j < l;j++){
                if(j+nums[j]<=maxStep)  continue;
                maxStep = j+nums[j];
                curr = j;
            }

            if(maxStep>=l-1)  break;
            i = curr;
        }
        return true;
    }
};

[wangqianqian202301]

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        length = len(nums)
        if length == 1 or length == 0:
            return True
        index = length - 2
        while nums[index] >= (length - index - 1):
            if self.canJump(nums[0:index]):
                return True
        return False

[X1AOX1A]

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        """思路同上"""
        _max = 0
        _len = len(nums)
        for i in range(_len-1):
            if _max < i:
                return False
            _max = max(_max, nums[i] + i)
            # 下面这个判断可有可无，但提交的时候数据会好看点
            if _max >= _len - 1:
                return True
        return _max >= _len - 1

[kangliqi1]

class Solution { public boolean canJump(int[] nums) { int n=nums.length; int k=0; for(int i=0;i<n;i++) { if(i>k){ return false; } // 能跳到最后一个位置 if(k>=n-1){ return true; } // 从当前位置能跳的最远的位置 k = Math.max(k, i+nums[i]); } return k >= n-1; } }

[Lydia61]

55. 跳跃游戏

代码

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[Jetery]

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return true;
        int mx = nums[0]; // 当前可到达最远距离
        for (int i = 0; i < n - 1; i++) {
            if (mx <= i && nums[i] == 0) return false;
            mx = max(mx, i + nums[i]);
        }
        return true;
    }
};

[JasonQiu]

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        pos = 0
        for index, num in enumerate(nums):
            if pos < index:
                return False
            if index + num > pos:
                pos = index + num
        return True

Time: O(n) Space: O(1)

[bookyue]

TC: O(n)
SC: O(1)

    public boolean canJump(int[] nums) {
        int max = 0;
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            if (i > max) return false;
            max = Math.max(max, nums[i] + i);
        }

        return true;
    }