解题思路

这是一个求最少跳跃次数的问题，可以通过贪心算法来解决：

  1. 维护当前能到达的最远位置
  2. 维护当前这一跳能到达的边界
  3. 维护最少跳跃次数
  4. 遍历数组时：
    • 更新当前能到达的最远位置
    • 当到达当前跳跃的边界时，更新边界并增加跳跃次数
  5. 如果最终不能到达终点，返回

代码

#include <iostream>
#include <vector>
using namespace std;

int minJumps(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return -1;
    if (n == 1) return 0;
    
    int maxReach = 0;  // 当前能到达的最远位置
    int curEnd = 0;    // 当前跳跃的边界
    int steps = 0;     // 跳跃次数
    
    for (int i = 0; i < n - 1; i++) {
        // 如果当前位置已经超过了能到达的最远位置
        if (i > maxReach) return -1;
        
        // 更新最远可达位置
        maxReach = max(maxReach, i + nums[i]);
        
        // 到达当前跳跃的边界
        if (i == curEnd) {
            steps++;
            curEnd = maxReach;
        }
    }
    
    // 判断是否能到达最后一个位置
    return maxReach >= n - 1 ? steps : -1;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    cout << minJumps(nums) << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static int minJumps(int[] nums) {
        int n = nums.length;
        if (n == 0) return -1;
        if (n == 1) return 0;
        
        int maxReach = 0;
        int curEnd = 0;
        int steps = 0;
        
        for (int i = 0; i < n - 1; i++) {
            if (i > maxReach) return -1;
            
            maxReach = Math.max(maxReach, i + nums[i]);
            
            if (i == curEnd) {
                steps++;
                curEnd = maxReach;
            }
        }
        
        return maxReach >= n - 1 ? steps : -1;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        
        System.out.println(minJumps(nums));
    }
}

def minJumps(nums):
    n = len(nums)
    if n == 0:
        return -1
    if n == 1:
        return 0
        
    max_reach = 0  # 当前能到达的最远位置
    cur_end = 0    # 当前跳跃的边界
    steps = 0      # 跳跃次数
    
    for i in range(n - 1):
        # 如果当前位置已经超过了能到达的最远位置
        if i > max_reach:
            return -1
            
        # 更新最远可达位置
        max_reach = max(max_reach, i + nums[i])
        
        # 到达当前跳跃的边界
        if i == cur_end:
            steps += 1
            cur_end = max_reach
            
    return steps if max_reach >= n - 1 else -1

n = int(input())
nums = list(map(int, input().split()))
print(minJumps(nums))

算法及复杂度

  • 算法：贪心算法
  • 时间复杂度： - 只需要遍历一次数组
  • 空间复杂度： - 只需要常数额外空间

这道题的关键在于使用贪心策略来计算最少跳跃次数。主要思路是：

  1. 维护三个重要变量：

    • ：当前能到达的最远位置
    • ：当前这一跳能到达的边界
    • ：已经进行的跳跃次数

  2. 贪心的策略：

    • 在遍历过程中不断更新
    • 只有在到达当前跳跃边界时才增加跳跃次数
    • 到达边界时，将下一次跳跃的边界更新为当前能到达的最远位置

  3. 特殊情况处理：

    • 数组长度为 时返回
    • 数组长度为 时返回
    • 如果在遍历过程中发现当前位置已经超过了能到达的最远位置，返回
    • 如果最终不能到达终点，返回

这种贪心的方法能够保证在可达终点的情况下找到最少的跳跃次数。