Jump Game - LeetCode

https://leetcode.com/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150

LeetCode_Sharing.png

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [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: nums = [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.

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 105

解析

问题背景

给定一个整数数组 nums，我们从数组的第一个位置开始，每个位置的数字表示我们可以从这个位置跳的最大长度。问题是判断是否可以跳到数组的最后一个位置。

思路

为了解决这个问题，我们采用了一种贪心的方法。主要的思想是，我们不需要计算从每个位置都可以到达的所有位置。我们只需要在每一步中更新可以达到的最远位置即可。

步骤

  1. 初始化最远可达位置：开始时，我们可以到达的最远位置为 0（即数组的第一个位置）。
  2. 遍历数组：我们遍历数组的每一个元素，并对每一个元素执行以下操作：
    • 检查当前位置是否可达：如果当前位置超过了我们之前计算的最远可达位置，那么说明当前位置不可达，因此我们也不可能到达数组的末尾。在这种情况下，我们直接返回 False。
    • 更新最远可达位置：如果当前位置是可达的，我们就更新最远可达位置。最远可达位置是当前位置加上当前位置的值和之前的最远可达位置中的较大者。
  3. 检查最后一个位置是否可达：遍历结束后，如果最远可达位置大于或等于数组的最后一个位置，那么说明数组的最后一个位置是可达的，返回 True。否则，返回 False。

为什么这个方法有效？

这个方法之所以有效，是因为我们始终尽量跳得更远。如果某个位置不可达，那么从这个位置后面的任何位置都不可能到达数组的末尾。

示例

考虑数组 nums = [2,3,1,1,4]：

  • 初始时，最远可达位置为 0。
  • 当我们在位置 0 时，可以跳 2 步，所以最远可达位置更新为 0 + 2 = 2。
  • 当我们在位置 1 时，可以跳 3 步，所以最远可达位置更新为 1 + 3 = 4，这已经超过了数组的长度，所以我们可以到达数组的末尾。

这种贪心的方法可以在 O(n) 的时间复杂度内判断是否可以到达数组的末尾，其中 n 是数组的长度。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_reach = 0
        target = len(nums) - 1

        for i, num in enumerate(nums):
            if i > max_reach:
                return False
            max_reach = max(max_reach, i + num)
            if max_reach >= target:
                return True
        return Fasle

class Solution {
    public boolean canJump(int[] nums) {
        int max_reach = 0;
        int target = nums.length - 1;
        for (int i = 0; i < nums.length; i++) {
            if (i > max_reach){
                return false;
            }
            max_reach = max_reach > (i + nums[i])?max_reach:(i + nums[i]);
            if(max_reach >= target){
                return true;
            }
        }
        return false;
    }
}

#include<iostream>
using std::vector;
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int max_reach = 0;
        int target = nums.size() - 1;

        for (int i = 0; i < nums.size(); ++i) {
            if (i > max_reach){
                return false;
            }
            max_reach = max_reach > (i + nums[i]) ? max_reach : (i + nums[i]);
            if (max_reach >= target){
                return true;
            }
        }
        return false;
    }
};

贪心算法的应用。