给定一系列非负整数, 每个值代表从此下标可以向前跳跃的最远距离, 试求出跳跃到数组尾端需要的最少步骤.
如给定 [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的更多相关文章
-
LeetCode 45. 跳跃游戏 II | Python
45. 跳跃游戏 II 题目来源:https://leetcode-cn.com/problems/jump-game-ii 题目 给定一个非负整数数组,你最初位于数组的第一个位置. 数组中的每个元素 ...
-
Java实现 LeetCode 45 跳跃游戏 II(二)
45. 跳跃游戏 II 给定一个非负整数数组,你最初位于数组的第一个位置. 数组中的每个元素代表你在该位置可以跳跃的最大长度. 你的目标是使用最少的跳跃次数到达数组的最后一个位置. 示例: 输入: [ ...
-
力扣Leetcode 45. 跳跃游戏 II - 贪心思想
这题是 55.跳跃游戏的升级版 力扣Leetcode 55. 跳跃游戏 给定一个非负整数数组,你最初位于数组的第一个位置. 数组中的每个元素代表你在该位置可以跳跃的最大长度. 你的目标是使用最少的跳跃 ...
-
[leetcode] 45. 跳跃游戏 II(Java)(动态规划)
45. 跳跃游戏 II 动态规划 此题可以倒着想. 看示例: [2,3,1,1,4] 我们从后往前推,对于第4个数1,跳一次 对于第3个数1,显然只能跳到第4个数上,那么从第3个数开始跳到最后需要两次 ...
-
leetcode 45. 跳跃游戏 II JAVA
题目: 给定一个非负整数数组,你最初位于数组的第一个位置. 数组中的每个元素代表你在该位置可以跳跃的最大长度. 你的目标是使用最少的跳跃次数到达数组的最后一个位置. 示例: 输入: [2,3,1,1, ...
-
[LeetCode] 45. 跳跃游戏 II
题目链接 : https://leetcode-cn.com/problems/jump-game-ii/ 题目描述: 给定一个非负整数数组,你最初位于数组的第一个位置. 数组中的每个元素代表你在该位 ...
-
【LeetCode】跳跃游戏II
[问题]给定一个非负整数数组,你最初位于数组的第一个位置.数组中的每个元素代表你在该位置可以跳跃的最大长度.你的目标是使用最少的跳跃次数到达数组的最后一个位置. 示例: 输入: [,,,,] 输出: ...
-
Leetcode力扣45题 跳跃游戏 II
原题目: 跳跃游戏 II 给定一个非负整数数组,你最初位于数组的第一个位置. 数组中的每个元素代表你在该位置可以跳跃的最大长度. 你的目标是使用最少的跳跃次数到达数组的最后一个位置. 示例: 输入: ...
-
LeetCode Single Number I / II / III
[1]LeetCode 136 Single Number 题意:奇数个数,其中除了一个数只出现一次外,其他数都是成对出现,比如1,2,2,3,3...,求出该单个数. 解法:容易想到异或的性质,两个 ...
随机推荐
-
Unity的安装和破解
网址:unity3d.com/cn/ unity的破解软件可以去unity圣典的网站上下载: 点击资源库,在资源库中找 下载过程中有时会提示需要对应的VS版本,忽略掉这个错误,并不需要最新的VS, ...
-
FastDFS 上传文件
[root@GW1 client]# ./fdfs_test ../conf/client.conf upload /home/tmp/1009.png This is FastDFS client ...
-
Day20 Django之Model多对多、中间件、缓存、信号和分页
一.Form补充 class IndexForm(forms.Form): # c = [ # (1, 'CEO'), # (2, 'CTO') # ] # 静态字段,属于IndexForm类,即使数 ...
-
php知识--递归
<?php // /* * 遍历输出文件夹中的所有内容 * @param1 string $dir,要遍历的路径 * @param2 int $level = 0,当前的级别 */ functi ...
-
iOS 即时视频和聊天(基于环信)
先上效果图: 屏幕快照 2015-07-30 下午5.19.46.png 说说需求:开发一个可以进行即时视频聊天软件. 最近比较忙,考完试回到公司就要做这个即时通信demo.本来是打算用xmpp协议来 ...
-
OpenCL——把vector变成scalar
https://*.com/questions/46556471/how-may-i-convert-cast-scalar-to-vector-and-vice-versa- ...
-
【转】Java HashMap的死循环
问题的症状 从前我们的Java代码因为一些原因使用了HashMap这个东西,但是当时的程序是单线程的,一切都没有问题.后来,我们的程序性能有问题,所以需要变成多线程的,于是,变成多线程后到了线上,发现 ...
-
JavaScript学习 - 基础(三) - 运算符
js运算符 1.算数运算符 包括 加(+) .减-() .乘(*).除(/).余数(%) 减号 还可以表示为 负号 例如: -1,-3 加号 还可以用于字符串拼接 例如: 'a' + 'b' = 'a ...
-
相邻行列相互影响的状态类问题(类似状压dp的搜索)(POJ3279)
POJ3279http://poj.org/problem?id=3279 题意:黑白的板,每次选择一个十字形翻转(十字板内黑白互换,若是边界则不管),求最小将原图变为全白的策略. 这是一道对于每个格 ...
-
编程哲学之C#篇:01——创世纪
我们能否像神一样地创建一个世界? 对于创建世界而言,程序员的创作能力最接近于神--相对于导演,作家,漫画家而言,他们创建的世界(作品)一旦完成,就再也不会变化,创建的角色再也不会成长.而程序员创建的世 ...