[LeetCode系列] 跳跃问题II

时间:2021-06-11 03:03:08

给定一系列非负整数, 每个值代表从此下标可以向前跳跃的最远距离, 试求出跳跃到数组尾端需要的最少步骤.

如给定 [2,3,1,1,4], 返回2. (从下标0跳到1, 从1跳到下标4).

算法描述: 贪心算法, 从头开始遍历数组, 记录通过ret+1步能够到达的最远下标为curr, 记录通过ret步能够到达的最远下标为last, 当遍历到的下标i大于上一次能够到达的最远下标last时, 更新last为curr, 并对ret加1, 数组遍历完成后返回ret.

代码:

 class Solution {
public:
int jump(int A[], int n) {
int last = ;
int curr = ;
int ret = ;
for (int i = ; i < n; i++) {
if (i > last) {
if (last == curr && last < n - ) return -;
last = curr;
ret++;
}
curr = max(curr, i + A[i]);
}
return ret;
}
};

[LeetCode系列] 跳跃问题II的更多相关文章

  1. LeetCode 45&period; 跳跃游戏 II &vert; Python

    45. 跳跃游戏 II 题目来源:https://leetcode-cn.com/problems/jump-game-ii 题目 给定一个非负整数数组,你最初位于数组的第一个位置. 数组中的每个元素 ...

  2. Java实现 LeetCode 45 跳跃游戏 II(二)

    45. 跳跃游戏 II 给定一个非负整数数组,你最初位于数组的第一个位置. 数组中的每个元素代表你在该位置可以跳跃的最大长度. 你的目标是使用最少的跳跃次数到达数组的最后一个位置. 示例: 输入: [ ...

  3. 力扣Leetcode 45&period; 跳跃游戏 II - 贪心思想

    这题是 55.跳跃游戏的升级版 力扣Leetcode 55. 跳跃游戏 给定一个非负整数数组,你最初位于数组的第一个位置. 数组中的每个元素代表你在该位置可以跳跃的最大长度. 你的目标是使用最少的跳跃 ...

  4. &lbrack;leetcode&rsqb; 45&period; 跳跃游戏 II&lpar;Java&rpar;&lpar;动态规划&rpar;

    45. 跳跃游戏 II 动态规划 此题可以倒着想. 看示例: [2,3,1,1,4] 我们从后往前推,对于第4个数1,跳一次 对于第3个数1,显然只能跳到第4个数上,那么从第3个数开始跳到最后需要两次 ...

  5. leetcode 45&period; 跳跃游戏 II JAVA

    题目: 给定一个非负整数数组,你最初位于数组的第一个位置. 数组中的每个元素代表你在该位置可以跳跃的最大长度. 你的目标是使用最少的跳跃次数到达数组的最后一个位置. 示例: 输入: [2,3,1,1, ...

  6. &lbrack;LeetCode&rsqb; 45&period; 跳跃游戏 II

    题目链接 : https://leetcode-cn.com/problems/jump-game-ii/ 题目描述: 给定一个非负整数数组,你最初位于数组的第一个位置. 数组中的每个元素代表你在该位 ...

  7. 【LeetCode】跳跃游戏II

    [问题]给定一个非负整数数组,你最初位于数组的第一个位置.数组中的每个元素代表你在该位置可以跳跃的最大长度.你的目标是使用最少的跳跃次数到达数组的最后一个位置. 示例: 输入: [,,,,] 输出: ...

  8. Leetcode力扣45题 跳跃游戏 II

    原题目: 跳跃游戏 II 给定一个非负整数数组,你最初位于数组的第一个位置. 数组中的每个元素代表你在该位置可以跳跃的最大长度. 你的目标是使用最少的跳跃次数到达数组的最后一个位置. 示例: 输入: ...

  9. LeetCode Single Number I &sol; II &sol; III

    [1]LeetCode 136 Single Number 题意:奇数个数,其中除了一个数只出现一次外,其他数都是成对出现,比如1,2,2,3,3...,求出该单个数. 解法:容易想到异或的性质,两个 ...

随机推荐

  1. Unity的安装和破解

    网址:unity3d.com/cn/   unity的破解软件可以去unity圣典的网站上下载: 点击资源库,在资源库中找 下载过程中有时会提示需要对应的VS版本,忽略掉这个错误,并不需要最新的VS, ...

  2. FastDFS 上传文件

    [root@GW1 client]# ./fdfs_test ../conf/client.conf upload /home/tmp/1009.png This is FastDFS client ...

  3. Day20 Django之Model多对多、中间件、缓存、信号和分页

    一.Form补充 class IndexForm(forms.Form): # c = [ # (1, 'CEO'), # (2, 'CTO') # ] # 静态字段,属于IndexForm类,即使数 ...

  4. php知识--递归

    <?php // /* * 遍历输出文件夹中的所有内容 * @param1 string $dir,要遍历的路径 * @param2 int $level = 0,当前的级别 */ functi ...

  5. iOS 即时视频和聊天&lpar;基于环信&rpar;

    先上效果图: 屏幕快照 2015-07-30 下午5.19.46.png 说说需求:开发一个可以进行即时视频聊天软件. 最近比较忙,考完试回到公司就要做这个即时通信demo.本来是打算用xmpp协议来 ...

  6. OpenCL——把vector变成scalar

    https://*.com/questions/46556471/how-may-i-convert-cast-scalar-to-vector-and-vice-versa- ...

  7. 【转】Java HashMap的死循环

    问题的症状 从前我们的Java代码因为一些原因使用了HashMap这个东西,但是当时的程序是单线程的,一切都没有问题.后来,我们的程序性能有问题,所以需要变成多线程的,于是,变成多线程后到了线上,发现 ...

  8. JavaScript学习 - 基础&lpar;三&rpar; - 运算符

    js运算符 1.算数运算符 包括 加(+) .减-() .乘(*).除(/).余数(%) 减号 还可以表示为 负号 例如: -1,-3 加号 还可以用于字符串拼接 例如: 'a' + 'b' = 'a ...

  9. 相邻行列相互影响的状态类问题(类似状压dp的搜索)(POJ3279)

    POJ3279http://poj.org/problem?id=3279 题意:黑白的板,每次选择一个十字形翻转(十字板内黑白互换,若是边界则不管),求最小将原图变为全白的策略. 这是一道对于每个格 ...

  10. 编程哲学之C&num;篇:01——创世纪

    我们能否像神一样地创建一个世界? 对于创建世界而言,程序员的创作能力最接近于神--相对于导演,作家,漫画家而言,他们创建的世界(作品)一旦完成,就再也不会变化,创建的角色再也不会成长.而程序员创建的世 ...