当前位置: 首页 > news >正文

算法练习13——跳跃游戏II

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]

转换问题 + 蛮力法

image.png

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)
# 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

以上是官方贪心解法,感觉并不足够“贪心”,更像是暴力解法,结合上图说一下我的理解:

  1. 首先一定能到,那么最多就n-1次跳跃,所以遍历每一次跳跃情况
  2. 第一次跳跃,发现可以跳到1、2,没到n-1,那么必然会【跳到1或2】,跳跃次数+1
  3. 第二次跳跃,会从1或2跳,可选位置,从1出发有2、3、4,从2出发有3,综合来看就是2、3、4,但是显然第一次就可以跳到2,第二次的2就可以忽略,实际上本次可忽略的位置就是本次可以跳到但是上次本就可以跳到的地方,而可忽略的位置由上次可以跳到的最远距离决定,第二次跳跃可忽略2本身及之前的位置,所以第二次跳跃【结果为3或4】,跳跃次数+1
  4. 第三次跳跃,会从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
http://www.lryc.cn/news/193064.html

相关文章:

  • 算法|每日一题|只出现一次的数字|位运算
  • Smartforms 打印出现的问题
  • 【考研408真题】2022年408数据结构41题---判断当前顺序存储结构树是否是二叉搜索树
  • 深度学习DAY3:激活函数
  • puppeteer
  • javascript二维数组(21)执行异步HTTP(Ajax)请求的方法($.get、$.post、$getJSON、$ajax)
  • TypeScript React(下)
  • 『Linux小程序』进度条
  • 【手写数字识别】GPU训练版本
  • c#-特殊的集合
  • Android 使用 eChart 设置标线
  • 红队专题-Cobalt strike 4.x - Beacon重构
  • 一文掌握 Go 文件的写入操作
  • 小程序入门及案例展示
  • linux 安装python django pip 遇到的问题
  • 【问题解决】【爬虫】抓包工具charles与pycharm发送https请求冲突问题
  • Hadoop3教程(二):HDFS的定义及概述
  • 【物联网+JAVA 】智慧工地源码
  • 001数据安全传输-多端协议传输平台:Openssl安装和配置 - EVP代码测试
  • 关于小编入坑第512天
  • VS2015编译Qt工程发生MSB4018错误完整解决过程
  • 如何使用JMeter测试导入接口/导出接口
  • [入门一]C# webApi创建、与发布、部署、api调用
  • 关于Vue+webpack使用unocss编写CSS,打包后CSS没加前缀
  • 软件工程与计算总结(十一)人机交互设计
  • Jmeter组件执行顺序与作用域
  • 第一天商城项目
  • C++笔记之通用多态函数包装器std::function
  • Linux命令(92)之passwd
  • 光电柴微电网日前调度报告