刷题55. Jump Game
2024-09-02 13:46:18
一、题目说明
题目55. Jump Game，给定一组非负数，从第1个元素起，nums[i]表示你当前可以跳跃的最大值，计算能否到达最后一个index。难度是Medium。
二、我的解答
非常惭愧，这个题目我做完，提交n次，除了几次边界错，其他就是Time Limit Exceeded，而且优化也无果。
我的代码：
class Solution{
public:
bool canJump(vector<int>& nums) {
vector<bool> dp(nums.size(),false);
dp[0] = true;
for(int i=0;i<nums.size();i++){
if(dp[i]){
for(int j=1;j<=nums[i]&&i+j<nums.size();j++){
if(dp[i]){
dp[i+j] = true;
}else{
return false;
}
}
}else{
return false;
}
}
return dp[nums.size()-1];
}
};
经过分析，上述代码是采用dp解答的，问题出在“从左到右”计算。如果“从右到左”，用不用dp都很容易解决：
class Solution{
public:
bool canJump(vector<int>& nums) {
//数组长度为1可以到达，如果nums[0]为0不可到达
if(nums.size()<=1)
return true;
else if(nums[0] == 0)
return false;
for(int i=nums.size()-2;i>0;i--){
//找到0，从前1个开始，判断能否跳过去
if(nums[i]==0){
int j=i-1;
while(j>=0){
if(nums[j]>(i-j)){
i = j;
break;
}else if(j==0)
return false;
j--;
}
}
}
return true;
}
};
性能：
Runtime: 16 ms, faster than 29.20% of C++ online submissions for Jump Game.
Memory Usage: 9.9 MB, less than 80.26% of C++ online submissions for Jump Game.
三、优化措施
看了大神的解答，十年苦读白费了。4行代码，可读性好，绝妙之极！
class Solution{
public:
//dp算法，从最后一个开始，last指示最后要能跳到的位置
bool canJump(vector<int>& nums) {
int last = nums.size() - 1;
for(int i = nums.size() - 2; i >= 0; i--)
if(last - i <= nums[i]) last = i;
return last == 0;
}
};
性能还不错：
Runtime: 12 ms, faster than 74.46% of C++ online submissions for Jump Game.
Memory Usage: 9.9 MB, less than 86.84% of C++ online submissions for Jump Game.
最新文章
- [Python]新手写爬虫全过程（已完成）
- HTML中属性ID和属性NAME有何区别？
- .NET： 配置文件
- C++之路进阶——codevs2366（朋友圈）
- android 点击edittext弹出软键盘，否则不弹
- ABAP OO与ALV结合方式探索(1)
- LeeCode 1-Two Sum
- uva111346Probability
- 寻找子串位置 codevs 1204
- linux xargs 使用
- Xamarin.Forms 初探
- rem 原理与简介
- 摘录<小王子>——[法]安东·圣埃克苏佩里
- Windows平台使用RMAN命令自动删除Oracle过期归档日志的方法
- Java多线程与线程同步
- Eclipse配置Maven的一些问题
- NameError: name 'reduce' is not defined
- MySQL数据库----基础操作
- java 静态方法 java 类中的方法无论静态还是非静态的都可以使用静态变量 而静态方法只能使用静态变量 (因为对象还没创建 所以不能在静态方法里面用this)
- am335x phy led problem