题解 | #跳跃游戏(二)#
跳跃游戏(二)
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
题解
这个题是跳跃游戏一的变体。要求最大的积分,实际上就是求路径上所有点的最大和。现在已知以下条件(如果有解):
- 最后一定停在n-1坐标
- 如果一个节点的坐标为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; }