学习记录：js算法（七十四）：跳跃游戏II

跳跃游戏II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
     
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2

思路一：贪心算法

function jump(nums) {
    let n = nums.length;
    if (n === 1) return 0; // 如果数组只有一个元素，不需要跳跃

    let jumps = 0, maxReach = 0, lastJumpPos = 0;

    for (let i = 0; i < n - 1; i++) {
        // 找到当前能跳到的最远位置
        maxReach = Math.max(maxReach, i + nums[i]);

        // 当前位置已经是上次跳跃能达到的最远位置，需要再进行一次跳跃
        if (i === lastJumpPos) {
            jumps++;
            lastJumpPos = maxReach; // 更新下次跳跃需要开始的位置
        }
    }

    return jumps;
}

讲解
这道题目的解决方案可以通过贪心算法来实现，核心思想是尽可能地让每次跳跃都能让我们到达更远的位置。

1. 理解问题
   给定一个非负整数数组nums，数组中的每个元素表示你从当前位置可以跳跃的最大长度，目标是到达数组的最后一个位置。要求找到到达最后一个位置所需的最小跳跃次数。
2. 初始设置
   ● 初始化jumps为0，表示跳跃次数。
   ● 初始化maxReach为0，用来记录当前能到达的最远位置。
   ● 初始化lastJumpPos为0，记录上一次跳跃后能到达的最远位置。
3. 遍历数组
   遍历数组nums，直到倒数第二个位置（因为到达最后一个位置时自然完成任务，无需额外跳跃）。
4. 在每次迭代中执行以下步骤：
   1. 更新最大可达位置：计算当前位置i加上其对应的跳跃能力nums[i]，取当前最大可达距离与这个值的最大者，更新maxReach。这样可以确保maxReach始终记录着以当前位置为起点能跳到的最远位置。
   2. 判断是否需要跳跃：如果当前遍历到了上一次跳跃所能达到的最远位置（即i === lastJumpPos），说明需要进行下一次跳跃。此时，jumps加1，并将lastJumpPos更新为当前的maxReach。这表示从当前位置开始，至少需要一次跳跃来覆盖剩余的距离。
5. 结果返回
   遍历结束后，jumps即为到达数组最后一个位置所需的最小跳跃次数。

为什么这种方法有效？

• 这种方法充分利用了贪心策略，每一步都试图做出最优选择，即尽可能通过较少的跳跃覆盖更远的距离。通过维护一个不断向前推进的“最远可达边界”，我们确保了在每次跳跃时都选择了最经济的方案，从而减少了总的跳跃次数。
  通过这种方式，我们避免了暴力搜索或复杂的动态规划状态转移，仅通过一次遍历就高效解决了问题。

思路二：动态规划

var jump = function (nums) {
    const n = nums.length;
    if (n <= 1) return 0; // 如果数组长度小于等于1，不需要跳跃

    const dp = new Array(n).fill(Infinity);
    dp[0] = 0; // 到达起点不需要跳跃

    for (let i = 0; i < n; i++) {
        for (let j = 1; j <= nums[i] && i + j < n; j++) {
            dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
        }
    }

    return dp[n - 1]; // 返回到达最后一个位置的最小跳跃次数
};

讲解
动态规划的思路是维护一个数组 dp，其中 dp[i] 表示到达索引 i 所需的最小跳跃次数。我们可以通过遍历每个位置来更新后续位置的跳跃次数。
实现步骤：

1. 初始化 dp[0] = 0，因为到达起点不需要跳跃。
2. 对于每个位置 i，遍历从 i 可以跳跃到的所有位置 j，并更新 dp[j]。
3. 返回 dp[n-1]，即到达最后一个位置所需的最小跳跃次数。

具体解析：

1. 输入和目标:
   • 输入是一个非负整数数组，每个元素表示在该位置可以跳跃的最大步数。
   • 目标是计算从数组的起始位置跳到最后一个位置所需的最小跳跃次数。
2. 处理特殊情况:
   • 首先检查数组的长度。如果长度小于或等于1，说明已经在最后一个位置，因此不需要进行任何跳跃，直接返回0。
3. 初始化动态规划数组:
   • 创建一个与输入数组等长的动态规划数组，用于存储到达每个位置的最小跳跃次数。初始时，所有位置的值都设置为无穷大，表示尚未计算。
   • 起始位置的跳跃次数设置为0，因为从起点到起点不需要跳跃。
4. 动态规划填充过程:
   • 遍历数组中的每个位置，针对每个位置，查看可以跳跃到的所有后续位置。跳跃的范围由当前元素的值决定，即从当前位置可以跳跃的最大步数。
   • 对于每一个可以到达的位置，更新到达该位置的最小跳跃次数。这个更新是通过比较当前已知的跳跃次数和从当前跳跃位置到达目标位置所需的跳跃次数（即增加一次跳跃）来完成的。
5. 返回结果:
   • 最后，返回到达数组最后一个位置的最小跳跃次数。

思路三：广度优先搜索 (BFS)

var jump = function (nums) {
    const n = nums.length;
    if (n <= 1) return 0; // 如果数组长度小于等于1，不需要跳跃

    let jumps = 0;
    let currentEnd = 0;
    let farthest = 0;
    const queue = [0]; // 从起点开始

    while (queue.length) {
        const size = queue.length; // 当前层的节点数
        jumps++;

        for (let i = 0; i < size; i++) {
            const index = queue.shift(); // 从队列中取出当前节点

            for (let j = 1; j <= nums[index] && index + j < n; j++) {
                if (index + j === n - 1) return jumps; // 如果到达最后一个位置，返回跳跃次数
                queue.push(index + j); // 将可以到达的位置加入队列
            }
        }
    }

    return jumps; // 返回到达最后一个位置的最小跳跃次数
};

讲解
BFS 可以用于寻找最短路径，因此我们可以将每个位置视为图中的节点，使用队列来进行广度优先搜索。

实现步骤：

1. 使用队列来存储当前可以到达的位置。
2. 每次从队列中取出一个位置，检查可以跳跃到的所有位置，并将它们加入队列。
3. 记录跳跃次数，直到到达最后一个位置。

具体解析：

1. 输入和目标:
   • 输入是一个非负整数数组，每个元素表示在该位置可以跳跃的最大步数。
     目标是计算从数组的起始位置跳到最后一个位置所需的最小跳跃次数。
2. 处理特殊情况:
   • 首先检查数组的长度。如果长度小于或等于1，说明已经在最后一个位置，因此不需要进行任何跳跃，直接返回0。
3. 初始化变量:
   • jumps: 用于记录跳跃次数，初始为0。
   • currentEnd: 记录当前跳跃能到达的最远位置，初始为0。
   • farthest: 记录在当前层中能够到达的最远位置，初始为0。
   • queue: 用于存储当前层的节点，从起点（索引0）开始。
4. 广度优先搜索过程:
   • 进入一个循环，直到队列为空。每次循环代表一个跳跃。
   • 在每次跳跃中，增加跳跃次数，并记录当前层的节点数（即可以访问的节点数）。
   • 遍历当前层的所有节点：
     1. 从队列中取出一个节点（当前位置）。
     2. 对于当前位置，计算可以跳跃到的所有后续位置。跳跃的范围由当前节点的值决定。
     3. 如果在跳跃过程中到达最后一个位置（数组的末尾），直接返回当前的跳跃次数。
   • 否则，将所有可以到达的位置加入队列，以便在后续的跳跃中访问。
5. 返回结果:
   如果队列为空但仍未达到最后一个位置，返回跳跃次数（这在正常情况下不会发生，因为题目保证可以到达最后一个位置）。

思路四：深度优先搜索 (DFS)

var jump = function (nums) {
    const n = nums.length;
    if (n <= 1) return 0; // 如果数组长度小于等于1，不需要跳跃

    let minJumps = Infinity;

    function dfs(index, jumps) {
        if (index >= n - 1) {
            minJumps = Math.min(minJumps, jumps);
            return;
        }

        for (let j = 1; j <= nums[index]; j++) {
            dfs(index + j, jumps + 1);
        }
    }

    dfs(0, 0); // 从起点开始 DFS
    return minJumps; // 返回到达最后一个位置的最小跳跃次数
};

讲解
DFS 也可以用来解决这个问题，但效率较低，因为它可能会遍历所有可能的路径。

实现步骤：

1. 从起点开始进行深度优先搜索，尝试跳跃到每个可能的位置。
2. 记录当前跳跃次数，并在到达最后一个位置时更新最小跳跃次数。

具体解析：

1. 输入和目标:
   • 输入是一个非负整数数组，每个元素表示在该位置可以跳跃的最大步数。
   • 目标是计算从数组的起始位置跳到最后一个位置所需的最小跳跃次数。
2. 处理特殊情况:
   • 首先检查数组的长度。如果长度小于或等于1，说明已经在最后一个位置，因此不需要进行任何跳跃，直接返回0。
3. 初始化变量:
   • minJumps: 用于记录达到最后一个位置所需的最小跳跃次数，初始设置为无穷大（Infinity），表示尚未找到有效的跳跃路径。
4. 深度优先搜索过程:
   • 定义一个递归函数 dfs(index, jumps)，其中 index 表示当前的位置，jumps 表示到达该位置所需的跳跃次数。
   • 在每次递归调用中，首先检查当前索引是否已经到达或超过最后一个位置。如果是，则更新 minJumps 为当前跳跃次数 jumps 和已有的 minJumps 的最小值。
   • 如果当前索引未到达最后位置，遍历从当前位置可以跳跃到的所有后续位置（由 nums[index] 决定的跳跃范围）。
   • 对于每一个可以跳跃到的位置，递归调用 dfs，将当前索引增加跳跃步数并将跳跃次数加1。
5. 开始搜索:
   • 调用 dfs(0, 0) 从起点开始进行深度优先搜索，初始跳跃次数为0。
6. 返回结果:
   • 最后返回 minJumps，即到达最后一个位置所需的最小跳跃次数。