文章目录
- 跳跃游戏
- 思路一:贪心算法
- 思路二:动态规划
- 思路三:递归 + 记忆化搜索
- 思路四:广度优先搜索 (BFS)
- 思路五:深度优先搜索 (DFS)
跳跃游戏
给你一个非负整数数组 nums ,你最初位于数组的 第一个 下标 。数组中的每个元素代表你在该位置可以跳跃的 最大长度 。
判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。
示例 1:
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2:
输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。
思路一:贪心算法
function canJump(nums) {let maxReach = 0; // 当前能到达的最远距离let currPos = 0; // 当前位置的索引for (let i = 0; i < nums.length; i++) {// 如果当前位置已经无法通过之前的跳跃到达,直接返回falseif (i > maxReach) return false;// 更新能到达的最远距离maxReach = Math.max(maxReach, i + nums[i]);// 如果最远距离已经可以到达最后一个位置,提前返回trueif (maxReach >= nums.length - 1) return true;// 移动到下一个位置currPos = i + 1;}// 如果遍历结束还没有返回,说明无法到达最后一个位置,返回falsereturn false;
}
讲解
解决这个问题,可以采用贪心算法的思路,动态规划也可以,但贪心算法更简洁高效。核心思想是维护一个可达到的最远距离,每次更新这个最远距离,并用它来决定>下一步的跳跃位置。
- 初始化:设置两个变量,maxReach 用来记录当前位置能够跳跃到的最远距离,currPos 用来记录当前所在位置的索引(初始为 0 )。
- 遍历:从数组的开始位置遍历,对于每个位置 i ,检查 i + nums[i] 是否大于 maxReach ,如果是,则更新 maxReach 为这个更大的值。这表示我们可以在当前位置通过一次跳跃到达更远的地方。
- 判断结束条件:如果在某次遍历中,currPos 加上当前步长能覆盖数组的最后一个位置,或者 maxReach 已经超过了数组的最后一个位置,说明可以到达数组的最后一个位置,返回 true 。反之,如果在遍历完数组之前,无法再进行有效跳跃(即 currPos 达到了 maxReach 但还没到达数组末尾),则返回 false 。
思路二:动态规划
var canJump = function (nums) {const dp = new Array(nums.length).fill(false);dp[0] = true; // 从第一个下标开始是可以到达的for (let i = 0; i < nums.length; i++) {if (dp[i]) {for (let j = 1; j <= nums[i] && i + j < nums.length; j++) {dp[i + j] = true; // 标记可以到达的下标}}}return dp[nums.length - 1]; // 返回最后一个下标是否可达
};
讲解
- DP 数组定义
我们定义一个布尔数组 dp,其中 dp[i] 表示从起始位置(第一个下标)到达下标 i 是否是可行的。初始时,dp[0] 为 true,因为我们一开始就在第一个下标。- 状态转移
- 初始化:dp[0] = true,表示起始位置是可达的。
- 遍历数组:对于每一个下标 i:
- 如果 dp[i] 为 true,表示可以从起始位置跳跃到 i ,那么我们可以尝试跳跃到 i 后面的下标。
- 根据 nums[i] 的值,计算可以跳跃到的范围:i + 1 到 i + nums[i]。
- 在这个范围内的每一个下标 j(确保 j 不超出数组边界),我们将 dp[j] 设置为 true,表示可以从起始位置跳跃到下标 j。
- 终止条件:如果在遍历过程中,发现 dp[nums.length - 1] 为 true,则说明可以到达最后一个下标,返回 true。如果遍历结束后仍然为 false,返回 false。
思路三:递归 + 记忆化搜索
function canJump(nums) {const memo = new Array(nums.length).fill(-1); // -1 表示未计算return canJumpFromPosition(0, nums, memo);
}function canJumpFromPosition(position, nums, memo) {if (position >= nums.length - 1) return true; // 已经到达或超过最后一个下标if (memo[position] !== -1) return memo[position] === 1; // 如果已经计算过,直接返回结果const furthestJump = Math.min(position + nums[position], nums.length - 1);for (let i = position + 1; i <= furthestJump; i++) {if (canJumpFromPosition(i, nums, memo)) {memo[position] = 1; // 标记为可达return true;}}memo[position] = 0; // 标记为不可达return false;
}
讲解
通过递归,我们可以尝试从当前下标跳跃到所有可能的下标,并记录已经计算过的结果,以避免重复计算。
- 基础条件:
- 如果当前下标 position 已经到达或超过最后一个下标,返回 true。
- 如果当前下标已经被访问过且结果为 false,则返回 false。
- 递归逻辑:
- 从当前位置 position,计算可以跳跃到的最远位置 furthestJump,即 position + nums[position],但不能超过数组边界。
- 对于从 position + 1 到 furthestJump 的每个下标,递归调用函数来检查是否可以到达最后一个下标。如果能达到,返回 true。
- 如果所有可能的跳跃都无法到达最后一个下标,则将当前位置标记为不可达,并返回 false。
- 记忆化搜索:
- 使用一个数组 memo 来存储每个下标的计算结果,避免重复计算。数组的初始值为 -1,表示尚未计算。
- 如果当前位置已经计算过,直接返回存储的结果。
思路四:广度优先搜索 (BFS)
var canJump = function (nums) {const queue = [0]; // 从第一个下标开始const visited = new Set(); // 用于记录访问过的下标while (queue.length > 0) {const current = queue.shift();if (current >= nums.length - 1) return true; // 如果已经到达最后一个下标for (let i = 1; i <= nums[current]; i++) {const next = current + i;if (next < nums.length && !visited.has(next)) {visited.add(next); // 标记为已访问queue.push(next); // 加入队列}}}return false; // 如果队列为空,返回 false
};
讲解
通过 BFS,我们可以逐层探索每个可跳跃的位置,直到找到是否能够到达最后一个下标。
- 初始化:
- 使用一个队列来存储当前可以访问的位置。
- 将起始位置(下标 0)加入队列。
- 使用一个布尔数组 visited 来标记已经访问过的位置,以避免重复访问。
- 遍历过程:
- 从队列中取出当前下标 current,检查是否已经到达最后一个下标。如果是,返回 true。
- 计算从 current 可以跳跃到的最远位置 furthestJump,即 current + nums[current]。
- 遍历从 current + 1 到 furthestJump 的所有下标,检查是否已经访问过。如果没有,则将这些下标加入队列,并标记为已访问。
- 终止条件:
- 如果队列为空且仍未到达最后一个下标,则返回 false。
思路五:深度优先搜索 (DFS)
function canJump(nums) {const visited = new Set();return dfs(0, nums, visited);
}function dfs(position, nums, visited) {if (position >= nums.length - 1) return true; // 已经到达最后一个下标if (visited.has(position)) return false; // 如果已经访问过,返回 falsevisited.add(position); // 标记为已访问const furthestJump = Math.min(position + nums[position], nums.length - 1);for (let i = position + 1; i <= furthestJump; i++) {if (dfs(i, nums, visited)) {return true; // 如果可以到达最后一个下标,返回 true}}return false; // 如果所有路径都不可达,返回 false
}
讲解
可以递归地尝试从当前位置跳跃到所有可能的下一个位置,直到达到最后一个下标或者确认无法到达。
- visited 数组:用于标记已经访问过的下标,以避免重复计算。
- dfs 函数:这是一个递归函数,接受当前下标 index 作为参数。
- 如果 index 超过或等于最后一个下标,返回 true。
- 如果当前下标已经访问过,返回 false。
- 标记当前下标为已访问后,获取当前下标的最大跳跃长度 maxJump。
- 遍历从 1 到 maxJump 的所有可能跳跃,递归调用 dfs。
- 如果在任何跳跃中能够到达最后一个下标,返回 true。
- 如果所有可能的跳跃都无法到达最后一个下标,返回 false。