LeetCode45——Jump Game II

刺骨的言语ヽ痛彻心扉 2022-08-09 12:41 31阅读 0赞

LeetCode45——Jump Game II

题意：

在一串序列中，每个索引对应的value表示你能跳的最大步数。

你在任何索引处可以跳\[1,value\]步，求跳到终点处的最小次数。

这题贪心就在于，假设在每个序列处我们都跳它的最大步数。

这里维护两个索引，一个是当前位置curIndex，一个是下一个最大位置nextIndex

现在假设有序列

\[2,3,1,1,4\]

按照如下步骤：

1.我们的当前位置curIndex = 0，我们从起点出发，我们跳到了最大位置index=2处，其value=1;

2.但是，很明显，如果在起点先跳一步到index=1，value=3处，我们能获取最小跳跃次数。

如何表示呢？

3.回到第1,步，我们需要进行如下迭代，也就是从上一个curIndex=2开始，我们比较nextIndex和index+nums\[index\]大小，来更新最大的nextIndex。

4.直到curIndex>=endIndex（这里curIndex表示的是更新过的，即用nextIndex替换过的），**为了加快迭代速度，由于是求最大值，就不用从上一次比较过的地方开始迭代。**

**也就是说：不需要增加变量j来记录开始时i的位置。**

代码：

class Solution {
    public:
    	int jump(vector<int>& nums) {
    		int endIndex = nums.size() - 1;
    		int nextIndex = 0;
    		int curIndex = 0;
    		int step = 0;
    		int i = 0;
    		while (i<nums.size())
    		{
    			if (curIndex >= endIndex)
    				break;
    			//int j = i;
    			while (i <= curIndex)
    			{
    				nextIndex = max(nextIndex, nums[i] + i);//greedy
    				//j++;
    				i++;
    			}
    			curIndex = nextIndex;
    			step++;
    		}
    		return step;
    	}
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，31人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode 45. Jump Game II (贪心)

目描述：每个点的数字代表可以从当前节点跳跃最远的节点数，比如 \[ 2, 3, 1, 1, 4 \] 第一个节点跳跃最远位置就是下标为2的第三个元素。求跳到最后一...

蔚落/ 2024年04月18日 11:01/ 0 赞/ 74 阅读

相关图解LeetCode：Jump Game II

在[上一篇文章中][Link 1]我们看到了Jump Game这道算法题，这个题目还有第二问，这就是LeetCode中的第45号题目，Jump Game II，题目还是给定一个

旧城等待，/ 2022年12月31日 03:28/ 0 赞/ 191 阅读

相关 leetcode 45. Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index

﹏ヽ暗。殇╰゛Y/ 2022年08月21日 04:44/ 0 赞/ 33 阅读

相关 LeetCode45——Jump Game II

LeetCode45——Jump Game II 题意：在一串序列中，每个索引对应的value表示你能跳的最大步数。你在任何索引处可以跳\[1,value\]步，求跳

刺骨的言语ヽ痛彻心扉/ 2022年08月09日 12:41/ 0 赞/ 32 阅读

相关 LeetCode 55/45 Jump Game I/II-----Greedy**

一：[Jump Game][] 题目： Given an array of non-negative integers, you are initially positio

ゝ一世哀愁。/ 2022年08月07日 12:47/ 0 赞/ 41 阅读

相关 LeetCode 45.Jump Game II (跳跃游戏II)

题目描述: 给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

约定不等于承诺〃/ 2022年05月11日 04:16/ 0 赞/ 222 阅读

相关 45. Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index

妖狐艹你老母/ 2022年03月21日 11:10/ 0 赞/ 181 阅读

相关【Leetcode】45. Jump Game II（动态规划）

Given an array of non-negative integers, you are initially positioned at the first index

待我称王封你为后i/ 2022年02月25日 01:57/ 0 赞/ 223 阅读

相关 45. Jump Game II

Given an array of non-negative integers, you are initially positioned at the first i

客官°小女子只卖身不卖艺/ 2022年02月16日 19:47/ 0 赞/ 204 阅读

相关 45. Jump Game II

description: Given an array of non-negative integers, you are initially positioned at

╰半橙微兮°/ 2021年11月01日 04:46/ 0 赞/ 277 阅读