零基础制作公司网站教程,泰州网站制作工具,哈尔滨公告最新消息,万素网LeetCode 45 跳跃游戏 II 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说#xff0c;如果你在 nums[i] 处#xff0c;你可以跳转到任意 nums[i j] 处: 0 j nums[i] i j n 返回…LeetCode 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]。 动态规划
dp[j]为跳到i位置所需的最少次数 实测能过但是耗时很高恰好数据集各项数量级每超出限制但凡0 nums[i] 1000加一点估计都过不了 提示: 1 nums.length 104 0 nums[i] 1000 题目保证可以到达 nums[n-1] class Solution:def jump(self, nums: List[int]) - int:length len(nums)if length 1:return 0dp [sys.maxsize] * lengthdp[0] 0for i in range(length):for j in range(i 1, min(i nums[i] 1, length)):dp[j] min(dp[j], dp[i] 1)return dp[length - 1]转换问题 蛮力法 class Solution:def jump(self, nums: List[int]) - int:n len(nums)maxPos, end, step 0, 0, 0for i in range(n - 1):if maxPos i:maxPos max(maxPos, i nums[i])if i end:end maxPosstep 1return step# 作者力扣官方题解
# 链接https://leetcode.cn/problems/jump-game-ii/
# 来源力扣LeetCode
# 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。以上是官方贪心解法感觉并不足够“贪心”更像是暴力解法结合上图说一下我的理解
首先一定能到那么最多就n-1次跳跃所以遍历每一次跳跃情况第一次跳跃发现可以跳到1、2没到n-1那么必然会【跳到1或2】跳跃次数1第二次跳跃会从1或2跳可选位置从1出发有2、3、4从2出发有3综合来看就是2、3、4但是显然第一次就可以跳到2第二次的2就可以忽略实际上本次可忽略的位置就是本次可以跳到但是上次本就可以跳到的地方而可忽略的位置由上次可以跳到的最远距离决定第二次跳跃可忽略2本身及之前的位置所以第二次跳跃【结果为3或4】跳跃次数1第三次跳跃会从3或4跳同理从3可以跳到4、5从4可以跳到5、6综合可以到达4、5、6忽略4跳跃结果为【5或6】显然此时就求出来了
代码写法上应该有两层循环第一层循环枚举的最多n-1次的跳跃次数第二层循环每一次跳跃中的可选位置巧的是把所有可选位置连起来正好是一次数组遍历所以一层循环就可以搞定
如果将end理解为本次跳跃中可忽略数值的上限maxPos理解为下次跳跃中可忽略数值的上限需要由本次跳跃备选项进行遍历计算得出一切则和官方算法一致或许if maxPos i还可省略
class Solution:def jump(self, nums: List[int]) - int:n len(nums)maxPos, end, step 0, 0, 0for i in range(n - 1):maxPos max(maxPos, i nums[i])if i end:end maxPosstep 1return step
