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

11-跳跃游戏

article 2025/2/25 21:30:06

给你一个非负整数数组 nums ，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

贪心算法思路分析

在遍历数组的过程中，我们需要不断更新当前能够到达的最远位置。对于数组中的每个位置，检查当前位置是否在最远可到达位置的范围内，如果不在，说明无法到达该位置，也就无法到达最后一个下标，直接返回 false；如果在范围内，更新最远可到达位置为当前位置能到达的最远位置和之前记录的最远可到达位置中的较大值。最后检查最远可到达位置是否大于等于数组的最后一个下标，如果是，则说明可以到达最后一个下标，返回 true，否则返回 false。

代码实现

function canJump(nums: number[]): boolean {
    const n = nums.length;
    let maxReach = 0; // 初始化最远可到达位置为 0

    for (let i = 0; i < n; i++) {
        // 如果当前位置超过了最远可到达位置，无法继续前进，返回 false
        if (i > maxReach) {
            return false;
        }
        // 更新最远可到达位置
        maxReach = Math.max(maxReach, i + nums[i]);
        // 如果最远可到达位置已经大于等于数组的最后一个下标，返回 true
        if (maxReach >= n - 1) {
            return true;
        }
    }
    return false;
}

// 示例调用
const nums = [2, 3, 1, 1, 4];
const result = canJump(nums);
console.log("是否能够到达最后一个下标:", result);

复杂度分析

时间复杂度： O(n)，其中是数组的长度。因为只需要对数组进行一次遍历。
空间复杂度： O(1)，只使用了常数级的额外变量 maxReach 来记录最远可到达位置。

代码解释

初始化：
- n 为数组的长度。
- maxReach 初始化为 0，表示最初最远可到达的位置是数组的第一个下标。
遍历数组：
- 对于数组中的每个位置 i，首先检查 i 是否超过了 maxReach，如果超过了，说明无法到达当前位置，直接返回 false。
- 然后更新 maxReach 为 maxReach 和 i + nums[i] 中的较大值，其中 i + nums[i] 表示从当前位置 i 能够到达的最远位置。
- 接着检查 maxReach 是否大于等于 n - 1，如果是，说明已经可以到达最后一个下标，返回 true。
返回结果：
- 如果遍历完整个数组都没有返回 true，则说明无法到达最后一个下标，返回 false。

这种贪心算法的思想通过不断更新最远可到达位置，在一次遍历中就可以判断是否能够到达数组的最后一个下标，效率较高。

动态规划思路

我们可以定义一个布尔类型的数组 dp，其中 dp[i] 表示是否能够到达数组的第 i 个位置。初始时，dp[0] 为 true，因为我们最初位于数组的第一个下标。然后，对于每个位置 i，我们检查之前的所有位置 j（0 <= j < i），如果 dp[j] 为 true 且从位置 j 能够跳到位置 i（即 j + nums[j] >= i），那么 dp[i] 也为 true。最后，dp[n - 1] 就表示是否能够到达数组的最后一个下标。

代码实现

function canJump(nums: number[]): boolean {
    const n = nums.length;
    // 初始化 dp 数组，dp[i] 表示是否能够到达第 i 个位置
    const dp: boolean[] = new Array(n).fill(false);
    // 最初位于第一个下标，所以 dp[0] 为 true
    dp[0] = true;

    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            // 如果能够到达位置 j 且从位置 j 能够跳到位置 i
            if (dp[j] && j + nums[j] >= i) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[n - 1];
}

// 示例调用
const nums = [2, 3, 1, 1, 4];
const result = canJump(nums);
console.log("是否能够到达最后一个下标:", result);

复杂度分析

时间复杂度：O(n^2)，其中是数组的长度。因为需要使用两层嵌套循环来填充 dp 数组。
空间复杂度：O(n)，主要用于存储 dp 数组。

代码解释

初始化 dp 数组：创建一个长度为 n 的布尔类型数组 dp，并将所有元素初始化为 false。将 dp[0] 设为 true，表示最初位于第一个下标。
填充 dp 数组：使用两层嵌套循环，外层循环遍历从 1 到 n - 1 的每个位置 i，内层循环遍历从 0 到 i - 1 的每个位置 j。对于每个位置 j，如果 dp[j] 为 true 且从位置 j 能够跳到位置 i（即 j + nums[j] >= i），则将 dp[i] 设为 true 并跳出内层循环。
返回结果：最终返回 dp[n - 1]，表示是否能够到达数组的最后一个下标。