已解决
跳跃游戏[中等]
来自网友在路上 11018101提问 提问时间:2023-11-23 23:59:00阅读次数: 101
最佳答案 问答题库1018位专家为你答疑解惑
优质博文:IT-BLOG-CN
一、题目
给你一个非负整数数组nums
,你最初位于数组的第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标,如果可以,返回true
;否则,返回false
。
示例 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 <= 104
0 <= nums[i] <= 105
二、代码
贪心: 提取题目重要信息可知:【1】当前下表i
+ 值nums[i]
是否可以到达下一个坐标i + 1
,当然之前的i + nums[i] >= 5
的时候,表示前5
个都可达;【2】只有满足1的条件时,如果可达 > 最大的下标,则直接返回true
否则,不断遍历获取最大值,直到大于最大下标返回true
或者遍历结束返回false
;
class Solution {public boolean canJump(int[] nums) {if (nums == null || nums.length == 0) {return false;}int len = nums.length;int pathlen = 0;// 如果可达路径大于等于下表表示可达,则判断是否大于数组的长度-1;for (int i = 0; i < len; i++) {if (pathlen >= i) {pathlen = Math.max(pathlen, i + nums[i]);if (pathlen >= len - 1) {return true;}}}return false;}
}
时间复杂度: O(n)
,其中n
为数组的大小。只需要访问nums
数组一遍,共n
个位置。
空间复杂度: O(1)
,不需要额外的空间开销。
查看全文
99%的人还看了
相似问题
- 【PyQt小知识 - 3】: QComboBox下拉框内容的设置和更新、默认值的设置、值和下标的获取
- 关于js中数组push之后长度明明有但是获取长度和随意的数组下标的时候不正常的问题
- 【C语言】数组下标为啥从0开始?下标越界访问一定报错吗?
- 寻找二维数组的最大值和对应下标 | C语言代码
- C++可以使用负数作为下标索引
- Python---字符串在计算机底层的存储形式---涉及索引下标
- 在excel中如何打出上标、下标
- 介绍一下标准的 CSS 的盒子模型?低版本 IE 的盒子模型有什么不同的?
- 代码随想录算法训练营二十四期第九天|LeetCode28. 找出字符串中第一个匹配项的下标、LeetCode459. 重复的子字符串
- axios的get请求时数组参数没有下标
猜你感兴趣
版权申明
本文"跳跃游戏[中等]":http://eshow365.cn/6-42106-0.html 内容来自互联网,请自行判断内容的正确性。如有侵权请联系我们,立即删除!