阳泉住房和城乡建设厅网站,官网设计模板,手机应用商店app下载官方版,网络推广企业网站推广策划书45. 跳跃游戏 II - 力扣#xff08;LeetCode#xff09;
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说#xff0c;如果你在 nums[i] 处#xff0c;你可以跳转到任意 nums[i j] 处:
0 LeetCode
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说如果你在 nums[i] 处你可以跳转到任意 nums[i j] 处:
0 j nums[i] i j n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
输入: nums [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置跳 1 步然后跳3步到达数组的最后一个位置。示例 2:
输入: nums [2,3,0,1,4]
输出: 2 思路和分析
本题相对于leetCode 55.跳跃游戏 贪心算法 难度增加了但是思路还是相似的还是要看最大的覆盖范围
贪心思路(O_O)?思考计算最少步数请问什么时候步数才一定要加一呢
① 局部最优当前可移动距离尽可能多走如果还没到终点步数再加一② 整体最优一步尽可能多走从而达到最少步数
真正解题的时候要从覆盖范围出发不管怎么跳覆盖范围内一定是可以跳到的以最小的步数增加覆盖范围覆盖范围一旦覆盖了终点得到的就是最少步数
需要统计两个覆盖范围当前这一步的最大覆盖和下一步最大覆盖
如果移动下标达到了当前这一步的最大覆盖最远距离了还没有到终点的话那么就必须再走一步来增加覆盖范围直到覆盖范围覆盖了终点 图中覆盖范围的意义在于只要红色的区域最多两步一定可以到不用管具体怎么跳反正一定可以跳到 C代码如下
class Solution {
public:// 贪心算法 时间复杂度: O(n) 空间复杂度: O(1)int jump(vectorint nums) {if (nums.size() 1) return 0;int cur 0;// 当前覆盖最远距离下标int next 0;// 下一步覆盖最远距离下标int result 0;// 记录走的最大步数for(int i0;inums.size()-1;i) {nextmax(inums[i],next);// 更新下一步覆盖最远距离下标if(i cur) {// 遇到当前覆盖最远距离下标if(cur ! nums.size()-1) {result; // 需要走下一步cur next;// 更新当前覆盖最远距离下标相当于加油了if(cur nums.size()-1 ) break; // 当前覆盖最远距到达集合终点不用做result操作了直接结束}else break;}}return result;}
};
来自代码随想录版本一
// 版本一
class Solution {
public:int jump(vectorint nums) {if (nums.size() 1) return 0;int curDistance 0; // 当前覆盖最远距离下标int ans 0; // 记录走的最大步数int nextDistance 0; // 下一步覆盖最远距离下标for (int i 0; i nums.size(); i) {nextDistance max(nums[i] i, nextDistance); // 更新下一步覆盖最远距离下标if (i curDistance) { // 遇到当前覆盖最远距离下标ans; // 需要走下一步curDistance nextDistance; // 更新当前覆盖最远距离下标相当于加油了if (nextDistance nums.size() - 1) break; // 当前覆盖最远距到达集合终点不用做ans操作了直接结束}}return ans;}
};时间复杂度: O(n)空间复杂度: O(1) 来自代码随想录版本二
// 版本二
class Solution {
public:int jump(vectorint nums) {int curDistance 0; // 当前覆盖的最远距离下标int ans 0; // 记录走的最大步数int nextDistance 0; // 下一步覆盖的最远距离下标for (int i 0; i nums.size() - 1; i) { // 注意这里是小于nums.size() - 1这是关键所在nextDistance max(nums[i] i, nextDistance); // 更新下一步覆盖的最远距离下标if (i curDistance) { // 遇到当前覆盖的最远距离下标curDistance nextDistance; // 更新当前覆盖的最远距离下标ans;}}return ans;}
};
时间复杂度: O(n)空间复杂度: O(1)
理解本题的关键在于以最小的步数增加最大的覆盖范围直到覆盖范围覆盖了终点这个范围内最少步数一定可以跳到不用管具体是怎么跳的不纠结于一步究竟跳一个单位还是两个单位。
参考和推荐文章、视频 代码随想录 (programmercarl.com)
贪心算法最少跳几步还得看覆盖范围 | LeetCode 45.跳跃游戏II_哔哩哔哩_bilibili
