建网站的费用,优化软件seo排名,企业网站备案流程,做网站要什么专业1、题目#xff1a;
给你一个非负整数数组 nums #xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标#xff0c;如果可以#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。 2… 1、题目
给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。 2、分析特点
题目要求你最初位于数组的 第一个下标 判断你是否能够到达最后一个下标 思维转换如果我已经到了倒数最后一个位置到了倒数第二个位置。。。 当然想正着理解也可以 设想一下对于数组中的任意一个位置 yyy我们如何判断它是否可以到达根据题目的描述只要存在一个位置 x它本身可以到达并且它跳跃的最大长度为 xnums[x]这个值大于等于 y即 xnums[x]≥y那么位置 y 也可以到达。 换句话说对于每一个可以到达的位置 x它使得 x1,x2,⋯ ,xnums[x] 这些连续的位置都可以到达。 这样以来我们依次遍历数组中的每一个位置并实时维护 最远可以到达的位置。对于当前遍历到的位置 x如果它在 最远可以到达的位置的范围内那么我们就可以从起点通过若干次跳跃到达该位置因此我们可以用 xnums[x] 更新最远可以到达的位置。 在遍历的过程中如果 最远可以到达的位置 大于等于数组中的最后一个位置那就说明最后一个位置可达我们就可以直接返回 True 作为答案。反之如果在遍历结束后最后一个位置仍然不可达我们就返回 False 作为答案。 3、思路
从终点开始算判断终点之前是否有位置能到达终点。有就将当前点当做终点无则继续向前判断。当终点与起点重合时则能从起点跳到终点。 4、代码 public boolean canJump(int[] nums) {if(nums.length 1) return true let lennums.length-1for(let i nums.length-2;i 0;i--){if(nums[i] len-i){len i;}}return len 0;}5、复杂度分析 时间复杂度O(n)其中 nnn 为数组的大小。只需要访问 nums 数组一遍共 nnn 个位置。空间复杂度O(1)不需要额外的空间开销。 6、总结
从终点开始算判断终点之前是否有位置能到达终点。有就将当前点当做终点无则继续向前判断。当终点与起点重合时则能从起点跳到终点。 如果本文对你有帮助的话记得给一乐点个赞哦感谢
