55.Jump Game---dp
2024-08-26 16:28:11
题目大意:给一个数组,第i个位置的值表示当前可以往前走的最远距离,求从第一个位置能否顺利走到最后一个位置。例子如下:
法一(借鉴):DP,dp[i]表示从上一个位置走到当前位置时,剩余的可以往前走的距离。dp公式是:dp[i]=max(dp[i-1],nums[i-1])-1。代码如下(耗时5ms):
public boolean canJump(int[] nums) {
//dp[i]表示从上一个位置走到当前位置i时,还剩余的可往前走的步数是多少
int[] dp = new int[nums.length];
//dp[i] = max(dp[i- 1], nums[i - 1]) - 1
for(int i = 1; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], nums[i - 1]) - 1;
if(dp[i] < 0) {
return false;
}
}
return true;
}
法二(借鉴):贪心,每次都更新记录当前能到达的最远距离,如果最远距离小于当前到达的位置或已到达终点,则break,更新最远距离,i+nums[i]表示当前能到达的最远距离。代码如下(耗时5ms):
public boolean canJump(int[] nums) {
int ma = 0;
for(int i = 0; i < nums.length; i++) {
//如果最远距离小于当前位置,表示当前位置不可达
if(i > ma || ma >= nums.length - 1) {
break;
}
//更新最远距离
ma = Math.max(ma, i + nums[i]);
}
return ma >= nums.length - 1;
}
最新文章
- MySQL自增ID 起始值 修改方法
- TFS修改项目名称
- uvm - dut
- td元素
- git使用命令, 特别:git checkout -b a 与 git branch a区别
- K2与OData和Swagger的集成
- jQuery(Keep for myself)
- 面试准备--Spring(IoC)
- 独立硬盘冗余阵列与HDFS
- Quartz实现定时任务的配置方法
- ubuntu 执行apt-get update 提示无法获得锁
- 生成ssl证书文件
- jQuery渐隐渐出的文字提示
- TreeView控件绑定数据库
- Ehcache 的简单实用 及配置
- Kotlin实践记录
- (后端)出现org.hibernate.NonUniqueResultException的原因即解决办法
- Google、微软、Linkedln、Uber、亚马逊等15+海外技术专家聚首2018TOP100Summit
- mongodb远程连接访问
- C语言之基本算法24—黄金切割法求方程近似根
热门文章
- Codeforces 627D Preorder Test(二分+树形DP)
- C++解析(11):对象的构造
- 【转】Oracle 查询库中所有表名、字段名、表名说明、字段名说明
- 使用StoryBoard执行动画
- Java SSM 整合
- Oracle 高性能SQL引擎剖析----执行计划
- Codeforces Round #409 (rated, Div. 2, based on VK Cup 2017 Round 2)
- docker基础学习
- 【SQL优化】MySQL官网中可优化的层次结构
- python自学笔记(二)