LeetCode题目（Python实现）：跳跃游戏

缺乏、安全感 2023-07-17 11:23 14阅读 0赞

### 文章目录 ###

*  题目
 *   *  想法一：逆序判断
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  贪心：从前往后
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  小结

# 题目 #

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

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

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

**示例1**：

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

**示例2**：

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

## 想法一：逆序判断 ##

就是从尾部开始，判断能否有前面位置能跳到尾部，如果有，则将该点重新设为尾部；如果没有直接返回false。重复进行直到尾部等于头部为止。

这个叫贪心算法的从后向前跳。

### 算法实现 ###

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

### 执行结果 ###

**执行结果** : 通过  
**执行用时** : 36 ms, 在所有 Python3 提交中击败了98.73%的用户  
**内存消耗** : 14.7 MB, 在所有 Python3 提交中击败了97.03%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

### 复杂度分析 ###

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

## 贪心：从前往后 ##

### 算法实现 ###

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

### 执行结果 ###

![在这里插入图片描述][20200321024007874.png]

### 复杂度分析 ###

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

## 小结 ##

刚开始想着从前往后，用贪心算法，但是出了点小问题，但是忽然反着一想，正向不行可以试试反向，于是居然顺利的解出了答案，并且还很快。

之后看了官方题解，了解了动态规划，然后又看到了贪心算法的从前往后的方法，也很快，原理是记录并不断更新当前节点可跳至最远的位置，最后与尾部位置进行比较。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: /images/20230528/7c5d495501864455b5c8df2bc1c4f10e.png
[20200321024007874.png]: /images/20230528/d71995c0fcce4d0882736b52b9819f4a.png