题解 | #跳跃游戏(二)#

跳跃游戏(二)

https://www.nowcoder.com/practice/58e31b785f4b4ced9695dd4fcd60c1ce

描述

给定一个非负整数数组nums,假定最开始处于下标为0的位置,数组里面的每个元素代表下一跳能够跳跃的最大长度,如果可以跳到数组最后一个位置,请你求出跳跃路径中所能获得的最多的积分。

1.如果能够跳到数组最后一个位置,才能计算所获得的积分,否则积分值为-1

2.如果无法跳跃(即数组长度为0),也请返回-1

3.数据保证返回的结果不会超过整形范围,即不会超过2^{31}-1231−1

数据范围:

00=nums.length=105

00=nums[i]=1000

题解

这个题是跳跃游戏一的变体。要求最大的积分,实际上就是求路径上所有点的最大和。现在已知以下条件(如果有解):

  1. 最后一定停在n-1坐标
  2. 如果一个节点的坐标为i,这个坐标的值为nums[i],对于任意大于i的正整数k,如果要能够跳到这个位置,必须有i+nums[i]>=k

根据以上条件我们可以反向推导,使用贪心法进行求解。假设我们在位置k上,那么如果可以从位置x < k上跳到位置k上,我们就可以将nums[x]累加到总的积分上。

那么如何确定是否可以从x上跳到k上呢?根据上面的第2点分析,只要x+nums[x] >= k即可。也就是nums[x] >= k - x,而k为上一个停留的位置,x为当前我们要判断的坐标。k的起始值为n-1,x的起始值为n-2,只要能满足上面的等式就将x--,然后更新k值。这里我们不使用坐标,而是使用从k和x之间的gap来进行求解。gap表示当前坐标i和上一坐标k之间的差值。

代码如下:

#include <bits/stdc++.h>

int solve(const std::vector<int> &v)
{
  if (v.size() <= 1)
  {
    return std::accumulate(v.begin(), v.end(), 0);
  }

  int ans = v.back();// 总的积分
  int gap = 1;// 上一个台阶和当前台阶之间的gap
  for (int i = v.size() - 2; i >= 0; --i)
  {
    if (v[i] >= gap)
    {
      gap = 1;
      ans += v[i];// 可以从i调到i+gap的位置,因此累加v[i],并且更新gap为1,表示是否可以从上一台阶调到当前
    }
    else if (i == 0)
    {
      return -1;// 已经找到开头了,表示无解
    }
    else
    {
      gap++;// 当前台阶无法跳到gap+i上,因此下一台阶需要将gap加一
    }
  }
  return ans;
}

int main()
{
  int n;
  std::cin >> n;
  std::vector<int> v(n);
  for (int i = 0; i < n; ++i)
  {
    std::cin >> v[i];
  }

  std::cout << solve(v) << std::endl;
  return 0;
}
全部评论

相关推荐

废铁汽车人:秋招真是牛鬼蛇神齐聚一堂
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
1
收藏
分享
牛客网
牛客企业服务