Java实现 LeetCode 45 跳跃游戏 II(二)
2024-10-09 05:24:17
45. 跳跃游戏 II
给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。
PS:
鉴于题目已经给了前提,那就是肯定能到达最后一个元素,那么只要考虑每一跳所能达到的最远位置就行了,也就是每次都选择最远可达的点,reach是当前需要进行跳跃的右界限,nextReach是下一次跳跃的右界限,nextReach的值一直动态更新,以保证每次跳跃都是最远的
class Solution {
public int jump(int[] nums) {
if(nums.length == 1) return 0;
int reach = 0;
int nextreach = nums[0];
int step = 0;
for(int i = 0;i<nums.length;i++){
nextreach = Math.max(i+nums[i],nextreach);
if(nextreach >= nums.length-1) return (step+1);
if(i == reach){
step++;
reach = nextreach;
}
}
return step;
}
}
最新文章
- C#设计模式之简单工厂模式(Simple Factory)
- Unreal4教程总结
- 用alarmmanager 多次发送PendingIntent
- Redis【知识点】批量删除指定Key
- JVM垃圾回收机制总结:调优方法
- BZOJ3566 : [SHOI2014]概率充电器
- 期望dp BZOJ3450+BZOJ4318
- CSS典型案例实践
- 兼容古董级IE小结
- linux在shell date获取时间的相关操作
- 【MySQL】TokuDB引擎初探(MySQL升级为Percona,MySQL升级为MariaDB)
- NSArray的排序
- SRM 441(1-250pt, 1-500pt)
- [Node.js] node-persist: localStorage on the server
- Organic Solar Cells - Generations of Solar Cells
- 网络协议 19 - RPC协议综述:远在天边近在眼前
- isinstance_issubclass
- Web API中给领域模型添加媒体类型支持
- 干货 | Elasticsearch 集群健康值红色终极解决方案【转】
- select()函数 的学习