网站开发哪里安全,班级网站成品,扁平化网站设计,建筑方案设计说明模板优质博文#xff1a;IT-BLOG-CN
一、题目
给你一个非负整数数组nums#xff0c;你最初位于数组的第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标#xff0c;如果可以#xff0c;返回true#xff1b;否则#xff0c;返…优质博文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;// 如果可达路径大于等于下表表示可达则判断是否大于数组的长度-1for (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)不需要额外的空间开销。
