[LeetCode-45] 基于贪心算法的跳跃游戏 II-最少跳跃次数的求解（C语言版）

/*

题目出处：LeetCode

题目序号：45. 跳跃游戏 II

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

*/

贪心策略：

每次跳跃从可选择的位置中选择跳到可以达到最远距离的位置。

思路：

（1）每次 index 变动时，跳跃次数加 1；

（2）结束条件判定：当 jump[ index ] ≥ length 时，跳跃次数加 1 结束。

程序清单

#include<stdio.h>

#define OK 1
typedef int Status;

Status TestJumpTimes(int *nums, int length) {
    int i; 
    int count = 0;        // 跳跃次数 
    int index = 0;        // 起点位置
    int jump[length];    // 记录当前位置可达到的最远距离 
    for(i = 0; i < length; i++){
        jump[i] = i + nums[i];
    } 
    if (length == 1) {
        printf("您已在终点，无需跳跃，所需的最少跳跃次数为 0 次。");    // 如果起始位置就是终点，则可以到达 
        return OK;
    }
    while(jump[index] < length - 1){
        int left = index + 1;
        int right =  jump[index]; 
        int temp = left;                        // 保存最远位置对应的索引 
        while (left < right) {                    // 寻找可跳的位置 
            if(jump[temp] < jump[left + 1]) {    
                temp = left + 1;
            }
            left++;
        }
        printf("\n");
        index = temp;         // 跳跃 
        count++;            // 跳跃次数加 1 
    }
    count = count + 1;        // 最后一次跳跃 
    printf("所需的最少跳跃次数为 %d 次。", count);
    return OK;
}

int main() {
    int n,i;
    printf("请输入您想测试的数组的长度：\n");
    scanf("%d",&n);
    int a[n];
    printf("请输入数组元素：\n");
    for (i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    TestJumpTimes(a,n);
    return 0;
}

运行结果