贪心算法:跳跃游戏II
2021/5/31 12:50:50
本文主要是介绍贪心算法:跳跃游戏II,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
45. 跳跃游戏 II
给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
思路
贪心的思路,局部最优:当前可移动距离尽可能多走,如果还没到终点,步数再加一。
整体最优:一步尽可能多走,从而达到最小步数。
从覆盖范围出发,不管怎么跳,覆盖范围内一定是可以跳到的,以最小的步数增加覆盖范围,覆盖范围一旦覆盖了终点,得到的就是最小步数。
这里需要统计两个覆盖范围,当前这一步的最大覆盖和下一步最大覆盖。
i等于当前覆盖最大距离下标, 需要再走一步(即ans++),因为最后一步一定是可以到的终点(题目假设总是可以到达数组的最后一个位置)。
i不等于覆盖最大距离下标,说明当前覆盖最远距离就可以直接达到终点了,不需要再走一步。
其精髓在于控制移动下标i只移动到nums.size() - 2的位置,移动下标只要遇到当前覆盖最远距离的下标,直接步数加一,不用考虑别的。
代码
public int jump(int[] nums) { int curDistance = 0; // 当前覆盖的最远距离下标 int ans = 0; // 记录走的最大步数 int nextDistance = 0; // 下一步覆盖的最远距离下标 for (int i = 0; i < nums.length - 1; i++) { // 注意这里是小于nums.size() - 1,这是关键所在 nextDistance = Math.max(nums[i] + i, nextDistance); // 更新下一步覆盖的最远距离下标 if (i == curDistance) { // 遇到当前覆盖的最远距离下标 curDistance = nextDistance; // 更新当前覆盖的最远距离下标 ans++; } } return ans; }
这篇关于贪心算法:跳跃游戏II的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现