为网站的特色功能设计各种模板,南京网站制作系统,站长统计ios,重庆招投标交易信息网个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程#xff0c;希望… 个人主页兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 目录 一、55. 跳跃游戏1️⃣题目描述2️⃣题目解析3️⃣解题代码 二、45. 跳跃游戏 II1️⃣题目描述2️⃣题目解析3️⃣解题代码 一、55. 跳跃游戏
点击直接跳转到该题目
1️⃣题目描述
给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。
示例1 输入nums [2,3,1,1,4] 输出true 解释可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。 示例2 输入nums [3,2,1,0,4] 输出false 解释无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。 注意
1 nums.length 1 0 4 10^{4} 1040 nums[i] 1 0 5 10^{5} 105
2️⃣题目解析
解题思路
维护一个可达到的最远位置maxPos通过遍历当前可跳跃范围内的所有位置计算每个位置能够达到的最远位置并更新maxPos。如果maxPos超过数组长度的最后一个位置则表示可以到达末尾返回true否则根据当前位置调整下一次可跳跃范围的起点和终点直到无法继续跳跃返回false。
3️⃣解题代码
class Solution {
public:bool canJump(vectorint nums) {int n nums.size(),left 0,right 0,maxPos 0;while(left right){if(maxPos n - 1) return true;for(int i left;i right;i)maxPos max(maxPos,i nums[i]);left right 1,right maxPos;}return false;}
};最后就顺利通过啦
二、45. 跳跃游戏 II
点击直接跳转到该题目
1️⃣题目描述
给定一个长度为 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 注意
1 nums.length 1 0 4 10^{4} 1040 nums[i] 1000题目保证可以到达 nums[n-1]
2️⃣题目解析
解题思路
每次在当前能跳跃范围内选择可以使得接下来能跳跃最远的位置不断更新可跳跃范围和最远位置直到到达最后一个位置。时间复杂度为O(n)其中n为数组长度。
3️⃣解题代码
class Solution {
public:int jump(vectorint nums) {int n nums.size(),left 0,right 0,maxPos 0,cnt 0;while(left right maxPos n - 1){cnt;for(int i left;i right;i)maxPos max(maxPos,i nums[i]);left right 1,right maxPos;}return cnt;}
};最后就顺利通过啦
