【Leetcode刷题记录】45. 跳跃游戏 II--贪心算法

45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

先分析题目给的第一个例子

输入: nums = [2,3,1,1,4]
输出: 2

从起点开始i=0,nums[i]=2，可以跳到i=1或i=2的位置。

• 如果跳到i=1处，由于nums[i]=3那么接下来最远可以跳到i=4处。
• 如果跳到i=2处，由于nums[i]=1,那么接下来最远可以跳到i=3处。

显然，我们要跳到i=1处，接着跳到i=4处，此时到达终点。在每一步中我们都尝试找到能让我们跳得最远的位置，从而确保在最少的跳跃次数内到达数组的最后一个位置。

那么这道题的贪心策略可以这样描述：

在任意一个起始点i上，我们不仅要考虑从该点可以直接跳跃的最大长度（nums[i]），还要考虑在这个范围内所有可能的下一步跳跃位置，并从中选择一个使得我们能够到达最远距离的位置进行跳跃。也就是$i+j+nums[i+j],其中1<=j<=nums[i]$的最大值。

代码

int jump(vector<int>& nums) {int time = 0;int n = nums.size(), i = 0;while (i < n - 1) {if (i + nums[i] >= n - 1) {time++;break;}int max = 0, maxIndex = 0;for (int j = 1; j <= nums[i]; j++) {if (i + j + nums[i + j] > max) {max = i + j + nums[i + j];maxIndex = i + j;}}i = maxIndex;time++;}return time;
}

除此之外还有一种贪心解法，我们的目标是到达数组最后一个位置，因此我们可以考虑最后一步跳跃前所在的位置，从起点往终点开始搜索，显然会出现有多个位置都可以跳跃到数组的最后一个位置的情况，那么我们选取距离最远的那个位置，找到一次跳跃前的位置后，继续按照这样的步骤，一直找到开始位置为止。

代码

int jump(vector<int>& nums) {int time=0;int position=nums.size()-1;while(position>0){for(int i=0;i<position;i++){if(i+nums[i]>=position){time++;position=i;break;}}}return time;
}