当前位置:网站首页>Algorithm---Jumping Game (Kotlin)
Algorithm---Jumping Game (Kotlin)
2022-08-11 10:03:00 【Xiaomi Technology Android R&D Cao Xinyu】
题目
给定一个非负整数数组 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]Indicates whether it is possible to jump toi的位置,We just need to start with the array,If the current location can jump to,Then set the interval from the current bit to the jump totrue,If the last bit of the array is true,That means it can be achieved
方法二:The array of the first method can be removed 从第一个位置开始,Directly record a farthest position,within this furthest location,All positions can be adjusted.We make the furthest update on this basis
解决方法
方法一:
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.属于贪心算法,Try to get the maximum value at each step,Use brute force solutions,well written too,That is when the array is too large,效率太低,过不了.
2.Algorithms are the use of time and space,The first method might be fine,But unnecessary space is wasted.
边栏推荐
- Convolutional Neural Network System,Convolutional Neural Network Graduation Thesis
- Halcon算子解释
- WooCommerce Ecommerce WordPress Plugin - Make American Money
- 【无标题】超时超时超时超时超时
- Adobe LiveCycle Designer report designer
- TIOBE - 2022年8月编程语言排行
- Huawei WLAN Technology: AC/AP Experiment
- Primavera Unifier - AEM Form Designer Essentials
- 使用树莓派和OAK相机部署机器人视觉模型
- How to improve the efficiency of telecommuting during the current epidemic, sharing telecommuting tools
猜你喜欢
随机推荐
华为WLAN技术:AC/AP 实验
爆料!前华为微服务专家纯手打500页落地架构实战笔记,已开源
神经网络参数如何确定的,神经网络参数个数计算
使用.NET简单实现一个Redis的高性能克隆版(七-完结)
Deploying Robot Vision Models Using Raspberry Pi and OAK Camera
训练一个神经网络要多久,神经网络训练时间过长
深度神经网络与人脑神经网络哪些区域有一定联系?
Data middle platform program analysis and development direction
snapshot standby切换
VC6.0 +WDK 开发驱动的环境配置
Primavera Unifier custom report creation and print sharing
HDRP Custom Pass Shader 获取世界坐标和近裁剪平面坐标
MySQL约束
Oacle数据库使用问题
idea插件自动填充setter
【Prometheus】Alertmanager告警全方位讲解
Primavera Unifier advanced formula usage sharing
数据库 SQL 优化大总结之:百万级数据库优化方案
基于卷积的神经网络系统,卷积神经网络毕业论文
Software custom development - the advantages of enterprise custom development of app software