给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
贪心算法思路分析
在遍历数组的过程中，我们需要不断更新当前能够到达的最远位置。对于数组中的每个位置，检查当前位置是否在最远可到达位置的范围内，如果不在，说明无法到达该位置，也就无法到达最后一个下标，直接返回 false；如果在范围内，更新最远可到达位置为当前位置能到达的最远位置和之前记录的最远可到达位置中的较大值。最后检查最远可到达位置是否大于等于数组的最后一个下标，如果是，则说明可以到达最后一个下标，返回 true，否则返回 false。
代码实现
function canJump(nums: number[]): boolean {const n = nums.length;let maxReach = 0; // 初始化最远可到达位置为 0for (let i = 0; i < n; i++) {// 如果当前位置超过了最远可到达位置，无法继续前进，返回 falseif (i > maxReach) {return false;}// 更新最远可到达位置maxReach = Math.max(maxReach, i + nums[i]);// 如果最远可到达位置已经大于等于数组的最后一个下标，返回 trueif (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] 为 truedp[0] = true;for (let i = 1; i < n; i++) {for (let j = 0; j < i; j++) {// 如果能够到达位置 j 且从位置 j 能够跳到位置 iif (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]，表示是否能够到达数组的最后一个下标。
虽然动态规划的方法可以解决这个问题，但由于其时间复杂度较高，在处理大规模数组时性能可能不如贪心算法。贪心算法的时间复杂度为 O(n)，空间复杂度为 O(1) ，是更优的解决方案。