10— 达到末尾下标所需的最大跳跃次数【LeetCode2770】
10— 达到末尾下标所需的最大跳跃次数【LeetCode2770】
吃猫的鱼Code
发布于 2023-07-24 18:32:33
发布于 2023-07-24 18:32:33
题目
2770. 达到末尾下标所需的最大跳跃次数 - 力扣（LeetCode）
给你一个下标从 0 开始、由 n 个整数组成的数组 nums 和一个整数 target 。
你的初始位置在下标 0 。在一步操作中，你可以从下标 i 跳跃到任意满足下述条件的下标 j ：
0 <= i < j < n-target <= nums[j] - nums[i] <= target
返回到达下标 n - 1 处所需的 最大跳跃次数 。
如果无法到达下标 n - 1 ，返回 -1 。
示例一：
输入：nums = [1,3,6,4,1,2], target = 2
输出：3
解释：要想以最大跳跃次数从下标 0 到下标 n - 1 ，可以按下述跳跃序列执行操作：
- 从下标 0 跳跃到下标 1 。
- 从下标 1 跳跃到下标 3 。
- 从下标 3 跳跃到下标 5 。
可以证明，从 0 到 n - 1 的所有方案中，不存在比 3 步更长的跳跃序列。因此，答案是 3 。 示例二：
输入：nums = [1,3,6,4,1,2], target = 3
输出：5
解释：要想以最大跳跃次数从下标 0 到下标 n - 1 ，可以按下述跳跃序列执行操作：
- 从下标 0 跳跃到下标 1 。
- 从下标 1 跳跃到下标 2 。
- 从下标 2 跳跃到下标 3 。
- 从下标 3 跳跃到下标 4 。
- 从下标 4 跳跃到下标 5 。
可以证明，从 0 到 n - 1 的所有方案中，不存在比 5 步更长的跳跃序列。因此，答案是 5 。 示例三：
输入：nums = [1,3,6,4,1,2], target = 0
输出：-1
解释：可以证明不存在从 0 到 n - 1 的跳跃序列。因此，答案是 -1 。 提示：
2 <= nums.length == n <= 1000-109 <= nums[i] <= 1090 <= target <= 2 * 109
解题
解法一
思路
本题同样是用到动态规划，使用动态规划可以很简单地解决问题。
首先建立一个存储每个索引处最多的到达方法dp[]，dp[i]表示到达nums[i]的最多的步数。然后用两个for循环，第一个for循环用来走nums数组，将nums数组每个索引走到的最大次数都存进dp[i]当中，第二个for循环用来看前面的索引处能不能到达第一个for循环到达的i，要是能到达，取最长的步数存入dp[i]中。
存储最大步数：dp[i] = Math.max(dp[i],dp[j]+1);
解决
class Solution {
public int maximumJumps(int[] nums, int target) {
int length = nums.length;
//声明dp数组，用于动态规划，dp[i]记录的是到达nums[i]的长度
int dp[] = new int[length];
//默认索引0处的方法数为1
dp[0] = 1;
for(int i=1;i=-target && dp[j]!=0){
//可达且j也是可达，然后挑选最大的路进行记录
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
}
return dp[length-1]-1;
}
}结果
> 2023/07/17 18:33:35
解答成功:
执行耗时:15 ms,击败了95.33% 的Java用户
内存消耗:42.5 MB,击败了78.94% 的Java用户本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。