当前位置:网站首页>算法---跳跃游戏(Kotlin)
算法---跳跃游戏(Kotlin)
2022-08-11 09:58:00 【小米科技Android 研发曹新雨】
题目
给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 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 <= 3 * 104
0 <= nums[i] <= 105
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/jump-game
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解决思路
方法一:定义一个数组,dp[i]表示是否可以跳到i的位置,我们只需要从数组开始,如果当前位置可以跳到,那就把从当前的每一位到可以跳到的区间置为true,如果数组的最后一位是true,那就表示可以达到
方法二:第一个方法的数组可以去掉 从第一个位置开始,直接记录一个最远的位置,在这个最远的位置之内,所有的都可以位置都可以调到。我们在这个基础上进行最远距离的更新
解决方法
方法一:
fun canJump(nums: IntArray): Boolean {
val dp = Array(nums.size) {
false }
dp[0] = true
nums.forEachIndexed {
index, i ->
if (dp[index]) {
Arrays.fill(dp,index,(index + i + 1).coerceAtMost(nums.size),true)
}
}
return dp[nums.size - 1]
}
方法二
优化版本:
fun canJump3(nums: IntArray): Boolean {
var maxRight = nums[0]
nums.forEachIndexed {
index, i ->
if (index <= maxRight){
maxRight = maxRight.coerceAtLeast(index + i)
}
}
return maxRight >= nums.size - 1
}
总结
1.属于贪心算法,每一步都尽量获取到最大值,使用暴力解决的方法,也挺好写,就是当数组太大的时候,效率太低,过不了。
2.算法就是时间和空间的利用啊,第一个方法可能不错,但是浪费了没有必要的空间。
边栏推荐
- Oracle database use problems
- 基于PSO在满足可靠性的基础上实现费用最优MATLAB仿真(含完整matlab代码)
- 关于ts中的指针问题call,bind, apply
- php将form表单内容提交到数据库后中文变成??(问号)
- 神经网络参数如何确定的,神经网络参数个数计算
- dreamweaver网页设计作业制作 学生个人网页猫眼电影 WEB静态网页作业模板 大学生个人主页博客网页代码 dw个人网页作
- pycharm 取消msyql表达式高亮
- HDRP shader 获取像素深度值和法线信息
- Dreamweaver网页作业——紫罗兰永恒花园动漫价绍网页 7页,含有table表格,js表单验证还有首页视频。以及列表页。浮
- 基于卷积的神经网络系统,卷积神经网络毕业论文
猜你喜欢
Primavera Unifier advanced formula usage sharing
Three handshakes and four waves
pycharm 取消msyql表达式高亮
Network model (U - net, U - net++, U - net++ +)
假设检验:正态性检验的那些bug——为什么对同一数据,normaltest和ktest会得到完全相反的结果?
How to analyze the neural network diagram, draw the neural network structure diagram
MongoDB 非关系型数据库
【Prometheus】 Grafana数据与可视化
网络流行简笔画图片大全,关于网络的简笔画图片
华为WLAN技术:AC/AP 实验
随机推荐
Simple interaction between server and client
数据中台方案分析和发展方向
【剑指offer】左旋字符串,替换空格,还有类题!!!
错误代码: 1118 - Row size too large (> 8126). Changing some columns to TEXT or BLOB may help. In current
三次握手与四次挥手
WordpressCMS主题开发02-制作顶部header.php和footer.php
NT 内核函数原型大全
【Prometheus】Alertmanager告警全方位讲解
MySQL select count(*) count is very slow, is there any optimization solution?
【luogu CF1286E】Fedya the Potter Strikes Back(字符串)(KMP)(势能分析)(线段树)
同态加密简介HE
Oacle数据库使用问题
【每日一题】640. 求解方程
go基础之并发
unity shader 测试执行时间
MySQL表sql语句增删查改_修改_删除
Have you encountered this kind of error? flink-sql writes to clickhouse
分割学习(loss and Evaluation)
训练一个神经网络要多久,神经网络训练时间过长
数据库基础