衡阳网站建设mdawl,怎么删除网站里的死链接,收费网站模板,软件系统开发流程55. 跳跃游戏 - 力扣#xff08;LeetCode#xff09;
给你一个非负整数数组 nums #xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标#xff0c;如果可以#xff0c;返回 true #xff1b…55. 跳跃游戏 - 力扣LeetCode
给你一个非负整数数组 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 1040 nums[i] 105
题解
题目描述给定了一个非负整数数组nums其中数组中的每个元素表示再该位置的最大跳跃长度目的是判断是否能从第一个下标到达最后一个下标。
贪心算法非常适合这个问题这道题的方法是遍历数组并在每一步中根据当前位置和当前位置的跳跃长度更新最大可到达的下标。在任何一步遍历中如果最大可达的下标超过或等于最后一个下标则答案为true。如果迭代结束没有到达最后一个下标则答案为false。
class Solution {
public:bool canJump(vectorint nums) {int maxReach 0; // 最远能到达的位置for(int i 0; i nums.szie(); i){if(i maxReach) return false; // 如果当前位置已经超过了最远能到达的位置就返回false}// 更新最远能到达的位置maxReach max(maxReach, nums[i] i);if(maxReach nums.size() - 1) return true; // 如果最远能到达的位置已经超过了数组的长度就返回true}
};45. 跳跃游戏 II - 力扣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提示:
1 nums.length 1040 nums[i] 1000题目保证可以到达 nums[n-1]
题解
这个题是上一个题的进阶版它指在上题的基础上要求你找从第一个下标到最后一个下标所需跳跃的最小次数。
同样使用贪心的方法来解决思路是记录每一次迭代可到达的范围直到到达数组的最后一个下标。
同时引入两个变量
currentEnd记录每一次跳跃前下标的跳跃边界farthest记录跳跃的最远距离
每一次遍历我们都更新farthest为自身和当前下标inums[i]的最大值。这表示从当前位置可以到达的最大下标。
如果i达到currentEnd则表明我们已经到达当前跳跃的边界因为我们增加跳跃次数(1)并将currentEnd设置为farthest。这是我们在下一次跳跃中可以到达的位置范围。
更新currentEnd后如果currentEnd大于等于末尾我们就不需要继续遍历了
class Solution {
public:int jump(vectorint nums) {int jumps 0; // 跳跃次数int currentEnd 0; // 当前跳跃的边界int farthest 0; // 最远能跳到的位置if(nums.size() 1) return 0; // 如果数组长度为1就不用跳了直接返回0for(int i 0; i nums.size() - 1; i){farthest max(nums[i] i, farthest); // 更新最远能跳到的位置if(i currentEnd){ // 遇到边界就更新边界并且步数加一currentEnd farthest;jumps;if(currentEnd nums.size() - 1) return jumps; // 如果当前边界已经超过了数组的长度就不用再继续计算了}}return jumps;}
};
