建网站首页图片哪里找,263企业邮箱网页版登录,3d建模师容易找工作吗,浙江省网站建设与管理试卷题目
45. 跳跃游戏 II
中等
相关标签 贪心 数组 动态规划
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说#xff0c;如果你在 nums[i] 处#xff0c;你可以跳转到任意 nums[i j] 处…题目
45. 跳跃游戏 II
中等
相关标签 贪心 数组 动态规划
给定一个长度为 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] 思路和解题方法 我使用了贪心算法通过记录当前能够到达的最远距离 end 和在当前范围内能够到达的最远距离 max1 来求解最少需要跳跃的次数。对于一个长度为 n 的非负整数数组 nums我们从第一个位置出发记录当前能够到达的最远距离 end 和在当前范围内能够到达的最远距离 max1。然后从第一个位置遍历到数组倒数第二个位置依次更新能够到达的最远距离和跳跃次数直到到达数组最后一个位置。假设在位置 i 时能够到达的最远距离为 max1。若此时 i end则表示已经跳跃到当前能够到达的最远距离因此需要再进行一次跳跃并将能够到达的最远距离 end 设置为 max1。这样可以保证每次跳跃到达的位置必然是能够到达的最远距离中的某一个位置。 复杂度 时间复杂度: O(n) 时间复杂度应为 O(n)其中 n 是数组 nums 的长度。对于每个位置都只需要常数时间来更新当前能够到达的最远距离和判断是否需要跳跃并且只需遍历一次整个数组。 空间复杂度 O(1) 空间复杂度为 O(1)因为只使用了几个常量大小的变量来记录最远距离、跳跃次数等信息不随输入规模 n 的增加而增加额外的空间使用。 c 代码
class Solution {
public:int jump(vectorint nums) { //函数接收一个由非负整数组成的向量nums返回跳跃到最后一个位置所需的最少跳跃次数if(nums.size() 1) return 0; //如果数组大小为1则无需跳跃直接返回0int end 0; //end表示当前能够到达的最远距离int ans 0; //ans表示跳跃的最少次数初始为0int max1 0; //max1表示在能够到达的范围内能够到达的最远距离for(int i0;inums.size()-1;i) //循环处理数组中的每个元素注意不需要处理最后一个元素因为最后一个元素已经到达了{max1 max(nums[i]i,max1); //更新在能够到达的范围内能够到达的最远距离if(i end) //如果到达了当前能够到达的最远距离{end max1; //更新能够到达的最远距离ans; //增加跳跃次数}}return ans; //返回需要跳跃的最少次数}
};觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
