河北网站建设及推广,河北建设网站信息查询中心,做汽配外贸是在哪个网站做,动易网站 价格既股票买卖系列之后的第二组贪心算法题目#xff1a;跳跃游戏系列。这一篇介绍的两个问题#xff0c;其输入均为一个数组#xff0c;每个元素表示在该位置可以跳跃的最大长度。
55. Jump Game
You are given an integer array nums. You are initially positioned at the …既股票买卖系列之后的第二组贪心算法题目跳跃游戏系列。这一篇介绍的两个问题其输入均为一个数组每个元素表示在该位置可以跳跃的最大长度。
55. Jump Game
You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
Example 1:
Input: nums [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.Example 2:
Input: nums [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.问题描述
给定一个非负整数数组每个元素表示在该位置可以跳跃的最大长度。判断是否能够到达最后一个下标。
贪心策略
维护一个最远可到达的位置 max_reach。遍历数组更新 max_reach。如果 max_reach 超过最后一个下标则返回 True。
解题思路
这是一个典型的贪心算法问题。我们可以通过维护一个变量 max_reach 来记录当前能够到达的最远位置。遍历数组时更新 max_reach并检查是否能够到达或超过最后一个下标。
步骤
初始化 max_reach 0表示当前能够到达的最远位置。遍历数组 nums 如果当前位置 i 超过了 max_reach说明无法到达当前位置返回 false。更新 max_reach 为 max(max_reach, i nums[i])。如果 max_reach 已经大于或等于最后一个下标返回 true。 遍历结束后如果 max_reach 大于或等于最后一个下标返回 true否则返回 false。
bool canJump(vectorint nums) {int max_reach 0;for (int i 0; i nums.size(); i) {if (max_reach i) {return false;}max_reach max(max_reach, i nums[i]);if (max_reach nums.size() - 1) {return true;}}if (max_reach nums.size() - 1) {return true;}else {return false;}
}复杂度分析
时间复杂度只需要遍历数组一次时间复杂度为 O ( n ) O(n) O(n)其中 n n n 是数组的长度。空间复杂度只使用了常数级别的额外空间空间复杂度为 O ( 1 ) O(1) O(1)。
45. Jump Game II
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i j] where:
0 j nums[i] andi j n
Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].
Example 1:
Input: nums [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.Example 2:
Input: nums [2,3,0,1,4]
Output: 2解题思路
这是一个典型的贪心算法问题。我们需要找到到达最后一个下标的最小跳跃次数。可以通过维护两个变量来解决
当前跳跃范围[start, end]表示当前跳跃可以到达的范围。最远可到达位置max_reach表示在当前跳跃范围内能够到达的最远位置。
步骤
初始化 jumps 0记录跳跃次数。end 0当前跳跃范围的结束位置。max_reach 0当前跳跃范围内能够到达的最远位置。 遍历数组 nums 更新 max_reach 为 max(max_reach, i nums[i])。如果当前位置 i 到达了当前跳跃范围的结束位置 end 增加跳跃次数 jumps。更新 end 为 max_reach表示进入下一个跳跃范围。 返回 jumps。
int jump(vectorint nums) {int jumps 0; // 记录跳跃次数int end 0; // 当前跳跃范围的结束位置int max_reach 0; // 当前跳跃范围内能够到达的最远位置for (int i 0; i nums.size() - 1; i) {max_reach max(max_reach, i nums[i]);// 如果当前位置到达了当前跳跃范围的结束位置if (i end) {jumps; // 增加跳跃次数end max_reach; // 更新跳跃范围}}return jumps;
}复杂度分析
时间复杂度只需要遍历数组一次时间复杂度为 O ( n ) O(n) O(n)其中 n n n 是数组的长度。空间复杂度只使用了常数级别的额外空间空间复杂度为 O ( 1 ) O(1) O(1)。
