跳跃游戏 II

题目要求

给定一个非负整数数组 nums，数组的长度为 n，数组的索引从 0 开始。数组中的每个元素 nums[i] 表示从位置 i 出发，能够向前跳跃的最大长度。在位置 i，可以跳跃到位置 i + j，其中 0 <= j <= nums[i] 且 i + j < n。目标是计算从数组的起始位置 nums[0] 跳跃到数组的最后一个位置 nums[n - 1] 所需的最小跳跃次数。题目保证所有生成的测试用例都能够到达最后一个位置。

解题思路

这个问题可以通过贪心算法来解决。贪心算法的核心思想是，在每一步跳跃中，尽可能地跳到能够使得后续跳跃选择最多的位置。具体的解题步骤如下：

初始化当前能够到达的最远位置 maxReach 为 nums[0]，初始化当前跳跃的最远位置 end 为 nums[0]，初始化跳跃次数 jumps 为 1（因为至少需要跳跃一次）。
遍历数组 nums，从索引 1 到 n - 1：
- 对于每个位置 i，更新能够到达的最远位置 maxReach，即 maxReach = max(maxReach, i + nums[i])。
- 如果当前位置 i 等于当前跳跃的最远位置 end，说明需要进行一次新的跳跃：
  - 更新跳跃次数 jumps，即 jumps++。
  - 更新当前跳跃的最远位置 end 为当前能够到达的最远位置 maxReach。
- 如果在遍历过程中 end 已经到达或超过了最后一个位置 n - 1，则可以停止遍历，因为已经可以到达最后一个位置。
遍历完成后，jumps 就是到达最后一个位置所需的最小跳跃次数。

这种方法的时间复杂度是 O(n)，因为它只需要遍历数组一次。空间复杂度是 O(1)，因为它只需要常数级别的额外空间。

Golang 版本

package main

import (
	"fmt"
)

func jump(nums []int) int {
	n := len(nums)
	if n < 2 {
		return 0
	}

	maxReach, end, jumps := nums[0], nums[0], 1

	for i := 1; i < n; i++ {
		if i > maxReach {
			break
		}
		maxReach = max(maxReach, i+nums[i])
		if i == end {
			if i != n-1 {
				jumps++
				end = maxReach
			}
		}
	}

	return jumps
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	nums := []int{2, 3, 1, 1, 4}
	fmt.Println("Minimum number of jumps to reach end is:", jump(nums))
}

这段代码定义了一个 jump 函数，它接受一个整数数组 nums 作为输入，并返回到达数组末尾所需的最小跳跃次数。main 函数中给出了一个示例数组，并打印出调用 jump 函数的结果。

C++版本

#include <iostream>
#include <vector>
#include <algorithm>

int jump(std::vector<int>& nums) {
    int n = nums.size();
    if (n < 2) return 0;

    int maxReach = nums[0];
    int step = nums[0];
    int jump = 1;

    for (int i = 1; i < n; ++i) {
        if (i == n - 1) {
            return jump;
        }
        maxReach = std::max(maxReach, i + nums[i]);
        step--;
        if (step == 0) {
            jump++;
            if (i >= maxReach) {
                return -1; // Cannot move forward from current position
            }
            step = maxReach - i;
        }
    }
    return jump;
}

int main() {
    std::vector<int> nums = {2, 3, 1, 1, 4};
    std::cout << "Minimum number of jumps to reach end is: " << jump(nums) << std::endl;
    return 0;
}

这段 C++代码实现了一个 jump 函数，它接受一个整数类型的 vector 作为输入，并返回到达 vector 末尾所需的最小跳跃次数。main 函数中提供了一个示例 vector 并打印出调用 jump 函数的结果。代码中使用了 <algorithm> 头文件中的 std::max 函数来计算最远能到达的位置。

Python 版本

def jump(nums):
    if len(nums) < 2:
        return 0

    max_reach, step, jump = nums[0], nums[0], 1

    for i in range(1, len(nums)):
        if max_reach >= len(nums) - 1:
            return jump

        if i > max_reach:
            break

        max_reach = max(max_reach, i + nums[i])
        step -= 1

        if step == 0:
            jump += 1
            step = max_reach - i

    return jump

# Example usage:
nums = [2, 3, 1, 1, 4]
print("Minimum number of jumps to reach end is:", jump(nums))

这段 Python 代码定义了一个 jump 函数，它接受一个列表 nums 作为输入，并返回到达列表末尾所需的最小跳跃次数。在示例使用中，给出了一个列表并打印出调用 jump 函数的结果。

Java 版本

public class Solution {
    public int jump(int[] nums) {
        if (nums.length < 2) return 0;

        int maxReach = nums[0];
        int step = nums[0];
        int jump = 1;

        for (int i = 1; i < nums.length; i++) {
            if (i == nums.length - 1) {
                return jump;
            }

            maxReach = Math.max(maxReach, i + nums[i]);
            step--;

            if (step == 0) {
                jump++;
                step = maxReach - i;
            }
        }
        return jump;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 3, 1, 1, 4};
        System.out.println("Minimum number of jumps to reach end is: " + solution.jump(nums));
    }
}

这段 Java 代码定义了一个 Solution 类，其中包含一个 jump 方法，用于计算并返回到达数组末尾所需的最小跳跃次数。main 方法中创建了一个 Solution 对象，并使用一个示例数组来调用 jump 方法，然后打印出结果。

Rust 版本

fn jump(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    if n < 2 {
        return 0;
    }

    let (mut max_reach, mut step, mut jump) = (nums[0] as usize, nums[0] as usize, 1);

    for i in 1..n {
        if i == n - 1 {
            return jump;
        }

        max_reach = max_reach.max(i + nums[i] as usize);
        step -= 1;

        if step == 0 {
            jump += 1;
            if i >= max_reach {
                return -1; // Cannot move forward from current position
            }
            step = max_reach - i;
        }
    }

    jump
}

fn main() {
    let nums = vec![2, 3, 1, 1, 4];
    println!("Minimum number of jumps to reach end is: {}", jump(nums));
}

这段 Rust 代码定义了一个 jump 函数，它接受一个 Vec<i32> 类型的参数 nums 并返回一个 i32 类型的结果，表示到达数组末尾所需的最小跳跃次数。main 函数中提供了一个示例数组，并打印出调用 jump 函数的结果。在 Rust 中，usize 类型用于索引和某些整数操作，因此在处理索引时将 i32 类型的数组元素转换为 usize。

总结

上述代码段展示了如何解决一个典型的跳跃游戏问题，即给定一个非负整数数组 nums，每个元素表示你在该位置可以跳跃的最大长度，目标是以最少的跳跃次数到达数组的最后一个位置。

解决方案的核心思想是使用贪心算法，通过以下步骤实现：

初始化三个变量：max_reach 表示当前能够到达的最远位置，step 表示在不增加跳跃次数的情况下还能走的最远距离，jump 表示已经跳跃的次数。
遍历数组，对于每个位置：
- 更新 max_reach 为当前位置加上该位置能跳的最大长度和当前 max_reach 的较大值。
- 每向前移动一步，step 减一。
- 当 step 为零时，说明需要进行新的跳跃，因此 jump 加一，并更新 step 为当前 max_reach 减去当前位置索引 i 的值。
当遍历到数组的最后一个位置时，返回 jump 作为结果。

这种方法的关键在于，它不需要遍历所有的跳跃路径，而是在每一步都做出局部最优的决策，从而保证了总体上的最优解。

在不同的编程语言版本中，这个算法的逻辑保持一致，只是语法和一些细节处理上有所不同。例如，在 Rust 中，索引操作使用 usize 类型，而在 Python 和 Java 中则直接使用整数类型。在 C++ 中，使用 std::max 函数来比较和更新最大值，而在 Python 中则使用内置的 max 函数。尽管实现的语言不同，但算法的核心思想和步骤是相同的。

hot-100