LeetCode--45. 跳跃游戏Ⅱ(C)

1. 题目描述

难度：困难

2. 题目分析

该题目是LeetCode55.跳跃算法的进阶版，有以下几点需要注意：

• 假设总可以到达数组的最后一个位置
• 要使用最少的跳跃次数

有两种实现方式：

• 最大跨越点算法
  找到能够到达最后一个元素的并且下标最小的点，也就是能达到最后一个元素的跨越程度的最大点。然后以此点开始，继续寻找能够到达此点的下标最小的点，知道找到的点的下标为0，也就是数组的首位。时间复杂度最好的情况是O(n)，最坏情况是O(n^2)
• 贪心算法
  从左到右遍历数组，计算每一步所能到达的最大距离，并更新最大距离值。当遍历的下标等于最大距离时，说明这个时候应该跳一步，直到遍历完数组。时间复杂度为O(n)

3. C语言实现

3.1 最大跨越点算法

代码如下：

// 寻找最大跨越点
int findMaxPoint(int* nums, int index){
    int i;
    for(i = 0; i < index; i++){
        if(nums[i]>= index-i)
            return i;
    }
    return i;
}
int jump(int* nums, int numsSize){
    int i, index, count;
    index = numsSize-1;
    count = 0;
    if(numsSize == 1) return 0;
    while(index != 0){
        index = findMaxPoint(nums, index);
        count++;
    }
    return count;
}

运行结果为：

3.2 贪心算法

代码如下：

int jump(int* nums, int numsSize){
	// ans为要跳跃的次数	
    int ans = 0;
    // end是目前为止，之前的元素能够到达的最大的点
    int end = 0;
    // maxPos是不断更新的最大值
    int maxPos = 0;
    for (int i = 0; i < numsSize - 1; i++)
    {
        maxPos = nums[i]+i>maxPos?nums[i]+i:maxPos;
        // 当遍历的下标遇到end时，说明该跳跃一步了，ans加一
        if (i == end)
        {
            end = maxPos;
            ans++;
        }
    }
    return ans;
}

运行结果为：