题解 | #跳跃游戏(三)#贪心解法

跳跃游戏(三)

https://www.nowcoder.com/practice/d92a70f4f42248d688b93c9e50d2e757

假设数组长度为n:

  1. 如果n等于0,则可以直接返回-1
  2. 如果n等于1,则可以直接返回0
  3. 当n大于0的时候,走第一步最远可以到达v[0]的索引位置,当我们要走到v[0]的索引位置的时候应该要走第二步,假设正整数k属于在区间[0,i],那么当v[k]+k取最大值的时候,也就是我们第二步从索引为k的位置起跳可以到达最远的位置。依次类推,我们使用len表示走step步的时候可以到达的最远距离,然后当len <= i的时候,我们要走第step+1步,此时选择[0,i]区间中能使v[k]+k取最大值的索引作为下一次起跳的位置,由于我们每次遍历的时候是可以计算每个v[i]+i的值,我们可以使用一个计数器来存放该值
时间复杂度:O(N),空间复杂度O(1)

代码如下:
int solve(const std::vector<int> &v)
{
  if (v.size() == 0)
  {
    return -1;
  }

  if (v.size() == 1)
  {
    return 0;
  }
  int len = v[0]; // 走1步的时候可以最远到达的索引位置
  int next = len; // 用于记录[0,v[0]+1]区间中v[k]+k的最大值
  int step = 1;   // 最少要走的步数
  for (int i = 1; i < v.size() - 1; ++i)
  {
    if (len <= i)
    {
      len = std::max(next, v[i] + i);
      step++;
    }
    else
    {
      next = std::max(next, v[i] + i);
    }

    if (len <= i)
    {
      return -1;
    }
    // 其实,这里可以判断len是否大于等于n-1,如果满足则可以跳出循环
  }
  return step;
}

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;
}


全部评论

相关推荐

野猪不是猪🐗:把你的学校加黑,加粗,斜体,下划线,描边,内阴影,内发光,投影,外发光,再上渐变色,居中,放大到最大字号,再把简历里其它内容删了,就行了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务