LeetCode--45. 跳跃游戏Ⅱ(贪心)

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;
}

运行结果为：