lintcode-116-跳跃游戏
2024-09-06 12:39:41
116-跳跃游戏
给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
判断你是否能到达数组的最后一个位置。注意事项
这个问题有两个方法，一个是贪心和 动态规划。
贪心方法时间复杂度为O（N）。
动态规划方法的时间复杂度为为O（n^2）。
我们手动设置小型数据集，使大家阔以通过测试的两种方式。这仅仅是为了让大家学会如何使用动态规划的方式解决此问题。如果您用动态规划的方式完成它，你可以尝试贪心法，以使其再次通过一次。样例
A = [2,3,1,1,4]，返回 true.
A = [3,2,1,0,4]，返回 false.标签
动态规划 贪心 数组
方法一（动态规划）
使用动态规划，用一维数组 dp[i] 表示假设位置 i 能够跳跃的最大长度
动态转移方程为：dp[i] = max(A[i]+i, dp[i−1]) [ if dp[i−1]≥i ]
code
class Solution {
public:
/**
* @param A: A list of integers
* @return: The boolean answer
*/
bool canJump(vector<int> A) {
// write you code here
int size = A.size();
if (size == 1) {
return true;
}
vector<int> dp(size, 0);
dp[0] = A[0];
for(int i=1; i<size; i++) {
if (dp[i-1] >= i) {
dp[i] = (A[i]+i > dp[i-1]) ? A[i]+i : dp[i-1];
}
else {
dp[i] = 0;
}
}
return dp[size-1] >= size-1;
}
};
方法二（贪心）
用一个变量代替 dp 数组
code
class Solution {
public:
/**
* @param A: A list of integers
* @return: The boolean answer
*/
bool canJump(vector<int> A) {
// write you code here
int size = A.size();
if (size == 1) {
return true;
}
int currMaxStep = A[0];
int step = 0;
for (int i=1; i<size; i++) {
if(i > currMaxStep) {
return false;
}
currMaxStep = (i+A[i] > currMaxStep) ? i+A[i] : currMaxStep;
if(currMaxStep >= size-1) {
return true;
}
}
return currMaxStep >= size-1;
}
};
最新文章
- CM添加kafka服务
- RDIFramework.NET 中多表关联查询分页实例
- LeetCode:Minimum Path Sum（网格最大路径和）
- [python学习笔记]Day1
- SAP中关于用户IP信息的获取(转载)
- 【风马一族_Java】如何使用ACSLL表的值，
- QT5控件-QDateTimeEdit和类QDateTime
- SDWebImage源码解读之干货大总结
- margin外边距合并问题以及解决方式
- springmvc 之 返回值
- GNU make 汇总
- vue学习之生命周期和钩子函数
- Luogu3527 POI2011 Meteors 整体二分、树状数组、差分
- 18-10-15 服务器删除数据的方法【Elasticsearch 数据删除 (delete_by_query 插件安装使用)】方法二没有成功
- Android dimen
- linux 时间戳
- Java Calendar,Date,DateFormat,TimeZone,Locale等时间相关内容的认知和使用(2) 自己封装的Calendar接口
- 【vue】vue项目引入 Element-UI
- TypeScript的数据类型总结
- Es6 类class的关键 super、static、constructor、new.target