Leetcode-055-跳跃游戏

Leecode-055-Jump Game

思路：贪心算法

题目描述

给定一个非负的整数数组，从0索引位置出发，看是否可以跳到数组最后一个元素。

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
// 可以从索引2的位置跳3步到最后一个位置

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.

Solution：贪心算法

我们可以用贪心的方法解决这个问题。

• 设想一下，对于数组中的任意一个位置 y，我们如何判断它是否可以到达？

  • 根据题目的描述，只要存在一个位置 x，它本身可以到达，并且它跳跃的最大长度为 x + nums[x]，这个值大于等于 y，即 x + nums[x]≥y，那么位置 y 也可以到达。
    <!--2-->
    
    
    

例子2：

[3, 2, 1, 0, 4]

# 1. 一开始在位置 0，可以跳跃的最大长度为 3，因此最远可以到达的位置被更新为 3；
# 2. 我们遍历到位置 1，由于 1≤3，因此位置 1 可达，加上它可以跳跃的最大长度2得到3，没有超过最远可以到达的位置；
# 3. 位置 2、位置 3 同理，最远可以到达的位置不会被更新；
# 4. 遍历到位置索引 4，由于 4>3，因此位置 4 不可达，我们也就不考虑它可以跳跃的最大长度了。
# 5. 返回false

Java

Solution :

class Solution{
    public boolean canJump(int[] nums){
        int n = nums.length;
        // rightmost用于更新跳的距离
        int rightmost = 0;

        // 遍历数组(注意这里的长度为n)
        for (int i = 0; i < n; i++) {
            // 如果当前位置i可达
            if (i <= rightmost){
                // 更新最远距离 i + nums[i]
                rightmost = Math.max(rightmost,i + nums[i]);
                // 如果最远距离可以跳到最后一个位置
                if (rightmost >= n - 1){
                    return true;
                }
            }
        }
        // 遍历结束仍然无法跳到最后一个位置
        return false;
    }
}

测试用例：

public static void main(String[] args) {
    int[] nums1 = {2,3,1,1,4};
    int[] nums2 = {3,2,1,0,4};
    Solution solution = new Solution();
    System.out.println(solution.canJump(nums2));
}

复杂度分析

• 时间复杂度：O(n) 其中n是数组的大小。这里只需要遍历nums数组一遍，一共有n个位置
• 空间复杂度：O（1）,不需要额外的开销

Python

Solution :

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

复杂度分析

• 时间复杂度：O(n) 其中n是数组的大小。这里只需要遍历nums数组一遍，一共有n个位置
• 空间复杂度：O（1）,不需要额外的开销

打赏