当前位置：首页 > article >正文

力扣经典题目之55.跳跃游戏

article 2025/1/15 22:38:30

2，解题思路

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

引言

在算法的世界里，有些问题看似简单，却蕴含着深刻的逻辑和策略。今天，我们将探讨一个经典的问题——跳跃游戏。这个问题不仅考验我们的逻辑思维，还涉及到如何高效地解决问题。让我们一起来看看如何通过简单的代码实现复杂的逻辑。

问题描述

跳跃游戏是一个经典的算法问题，它要求我们判断一个数组中的每个位置是否能够到达数组的最后一个位置。数组中的每个元素代表在该位置可以跳跃的最大长度。例如，nums = [2,3,1,1,4]，从位置0开始，我们可以跳到位置1或2，然后从这些位置继续跳跃，最终判断是否能够到达位置4。

解题思路

这个问题可以通过贪心算法来解决。贪心算法在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的。

初始化：首先，我们需要一个变量rightmost来记录当前能够到达的最远位置。初始时，rightmost为0，因为我们从数组的起始位置开始。
遍历数组：我们遍历数组中的每个位置i。对于每个位置，我们检查当前位置i是否在rightmost范围内。如果是，说明我们可以到达这个位置。
更新最远位置：如果可以到达位置i，我们更新rightmost为i + nums[i]和rightmost中的较大值。这表示从当前位置i跳跃后能够到达的最远位置。
提前终止：如果在任何时候rightmost大于或等于数组的最后一个位置（n - 1），我们立即返回true，表示可以到达数组的末尾。
最终判断：如果遍历完数组后，rightmost仍然没有达到数组末尾，我们返回false。