力扣45. 跳跃游戏 II
2023-12-24 05:49:19
贪心算法
- 思路:
- 在 pos 位置,能跳到 pos + nums[pos] 位置;
- 正向遍历数组,迭代出能跳到的最大位置:
-
maxPos = std::max(maxPos, idx + nums[idx]);
-
- 在遍历到最大位置的地方则更新步数,并重新统计基于此位置能跳到的最大位置;
class Solution {
public:
int jump(vector<int>& nums) {
int maxPos = 0;
int size = nums.size();
int step = 0;
int end = 0;
for (int idx = 0; idx < size - 1; ++idx) {
if (maxPos >= idx) {
maxPos = std::max(maxPos, idx + nums[idx]);
if (idx == end) {
end = maxPos;
++step;
}
}
}
return step;
}
};
文章来源:https://blog.csdn.net/N_BenBird/article/details/135176707
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!