NC206. 跳跃游戏(二)
描述
示例1
输入:
[2,4,2,1,0,100]
输出:
106
说明:
首先位于nums[0]=2，然后可以跳1步，到nums[1]=4的位置，积分=2+4=6，再跳到nums[5]=100的位置，积分=6+100=106 这样保证既能跳到数组最后一个元素，又能保证获取的积分最多示例2
输入:
[2,4,0,2,0,100]
输出:
108
说明:
跳跃路径为：2=>4=>2=>100，总共为108示例3
输入:
[2,3,2,1,0,100]
输出:
-1
说明:
跳不到最后一个位置，返回-1C++ 解法, 执行用时: 18ms, 内存消耗: 3000KB, 提交时间: 2022-07-11
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int maxJumpGrade(vector<int>& nums) {
// write code here
if(nums.size()==0)return -1;
vector<int>v(nums.size());
v[0]=nums[0];
for(int i=1;i<nums.size();++i)
{
if(nums[i-1]==0)
{
int n1=i-2;
while(n1>=0&&nums[n1]+n1<i)--n1;
if(n1<0)return -1;
else v[i]=v[n1]+nums[i];
}
else v[i]=v[i-1]+nums[i];
}
return v[nums.size()-1];
}
};
C++ 解法, 执行用时: 18ms, 内存消耗: 3000KB, 提交时间: 2021-12-23
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int maxJumpGrade(vector<int>& nums) {
// write code here
if(nums.size() == 0)
return -1;
int result = 0;
int targetPos = nums.size() - 1;
for(int i = nums.size() - 1; i >= 0; i--){
if(i + nums[i] >= targetPos){
result += nums[i];
targetPos = i;
}
}
if(targetPos != 0)
return -1;
else
return result;
}
};
C++ 解法, 执行用时: 18ms, 内存消耗: 3008KB, 提交时间: 2022-06-28
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int maxJumpGrade(vector<int>& nums) {
// write code here
//1.暴力法help1&help2
//用dp[i]存储i位置的最大积分，开始初始化为-1
if(nums.size()==0)
{
return -1;
}
vector<int> dp(nums.size(),-1);
dp[0]=nums[0];
//return help1(nums,dp);
//2.动态规划help0
return help0(nums);
}
int help0(vector<int>& nums)
{
//动态规划
if(nums.empty()) return -1;
int end=nums.size()-1;
int res=nums[end];
for(int i=nums.size()-2;i>=0;i--)
{
if(nums[i]+i>=end)
{
res+=nums[i];
end=i;
}
}
if(end==0) return res;
else return -1;
}
int help1(vector<int>& nums,vector<int>& dp)
{
//从前往后遍历O(k*n),k=maxlen(nums[i])
for(int i=0;i<nums.size();i++)
{
for(int j=1;j<=nums[i];j++)
{
if(dp[i]==-1)//中间出现-1说明最多只能到达这
{
return -1;
}
if((i+j)<dp.size())//只有nums不为0的位置才有可能到达末尾
dp[i+j]=max(dp[i+j],dp[i]+nums[i+j]);
}
}
return dp[nums.size()-1];
}
int help2(vector<int>& nums,vector<int>& dp)
{
//从后往前遍历O(n^2)
//dp[i]=max{dp[j]}+nums[i]
//其中j满足j<i&&j+nums[j]>=i
for(int i=1;i<nums.size();i++)
{
for(int j=0;j<i;j++)
{
if(j+nums[j]>=i)
{
dp[i]=max(dp[i],dp[j]+nums[i]);
}
}
}
return dp[nums.size()-1];
}
};
C++ 解法, 执行用时: 18ms, 内存消耗: 3008KB, 提交时间: 2022-02-17
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int maxJumpGrade(vector<int>& nums) {
// write code here
int len = nums.size();
//数组长度为0，直接返回-1
if(len==0) return -1;
//当前积分
int sum = nums[len-1];
//当前跳跃的终点位置
int curindex = len-1;
for(int i = len-2;i>=0;i--){
//只要能跳到curEnd位置，直接跟新积分值以及终点位置
if(i+nums[i] >= curindex){
sum += nums[i];
curindex = i ;
}
}
//如果最后能跟新到起始位置，直接返回grade，否则返回-1
return curindex == 0?sum:-1;
}
};
C++ 解法, 执行用时: 18ms, 内存消耗: 3048KB, 提交时间: 2021-12-14
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int maxJumpGrade(vector<int>& nums) {
if (nums.empty()) return -1;
int i = nums.size() - 1;
int ret = nums[i];
while (i > 0) {
int j = i - 1;
while (j>=0 && nums[j] + j < i) j--;
if (j < 0) return -1;
i = j;
ret += nums[i];
}
return ret;
}
};