LeetCode 045 Jump Game II
2024-09-06 02:26:37
题目要求:Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2
. (Jump 1
step from index 0 to 1, then 3
steps to the last index.)
代码如下:
class Solution {
public:
int jump(int A[], int n) { int step = 0;
int left = 0;
int right = 0; //用来记录局部点的最大步长 if(n == 1) return 0; while(left <= right){
step++;
const int old_right = right; //贪心算法
//局部最优解
for(int i = left; i <= old_right; i++){
//计算每次到达的地方(局部)
int new_right = i + A[i];
//如果new_right超过n-1,则表示到了结尾
if(new_right >= n - 1) return step;
//保证right是最大
if(new_right > right) right = new_right;
} //左值放在最优解的下一个
left = old_right + 1;
} return 0; }
};
最新文章
- C# 文章导航
- php分页原理
- Ubuntu 14.04 更换阿里云源
- 攻克Spring
- find exec 运用
- hadoop配置文件加载顺序(转)
- HTML5 File api 实现断点续传
- IIS部署FTP服务器步骤
- 全民Scheme(0):lat的定义
- 【EntityFramework 6.1.3】个人理解与问题记录(2)
- python3 进一步了解装饰器 NLP第四条
- centos7防火墙配置
- 配置php环境的一个nginx.conf
- python - 字符编码/格式化/替换符
- 一个简易的netty udp服务端
- django-CRM-项目部署
- js改变或添加className
- jqgrid 行选中multiboxonly属性说明
- HttpComponents-Client学习
- JS修改属性,六种数据类型
热门文章
- mysql管理表关系
- 微信小程序跳转到微信公众号
- CF1271E Common Number
- iNeuOS工业互联平台,WEB组态(iNeuView)增加工程视图导入、导出功能,及优化和修复,发布:v3.2.1版本
- Ubuntu17.10 React Native 环境搭建
- leetcode110:combination-sum-ii
- 易于理解的 python 深度学习摘要算法教程
- ElementUI表格行编辑单元格编辑支持(输入框,选择框)Demo
- Netty源码解析 -- 零拷贝机制与ByteBuf
- 这才是图文并茂:我写了1万多字,就是为了让你了解AQS是怎么运行的