seo网站建设公司哪家好,wordpress微博图床怎么用,中山营销型网站,网站建设及代运营合同题目链接
给你一个非负整数数组 nums #xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标#xff0c;如果可以#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
1 nums…题目链接
给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。
1 nums.length 1 0 4 10^4 1040 nums[i] 1 0 5 10^5 105
分析
假设当前位于nums[i]表示该元素后面的nums[i]个元素任我跳那该跳哪个呢
是不是得考虑跳到哪一个位置下下一步可以跳得更远。这个由indexnums[i]决定。
也就是说后面的nums[i]个元素里哪个索引元素值最大就跳到哪里。
/*** param {number[]} nums* return {boolean}*/
var canJump function (nums) {let i 0;let nextIndex;let maxVal 0;while (i nums[i] nums.length - 1) {if (nums[i] 0) {return false;}for (let j i 1; j i nums[i]; j) {if (j nums[j] maxVal) {nextIndex j;maxVal j nums[j];}}maxVal 0;i nextIndex;}return true;
};时间复杂度 O ( n 2 ) O(n^2) O(n2)
空间复杂度 O ( 1 ) O(1) O(1)
时间复杂度太高换个思路
维护一个最大可达位置maxReach。
/*** param {number[]} nums* return {boolean}*/
var canJump function (nums) {let maxReach0;for(let i0;inums.length;i){if(imaxReach){return false;}maxReachMath.max(maxReach,inums[i]);if(maxReachnums.length-1){return true;}}return true;
};时间复杂度 O ( n ) O(n) O(n)
空间复杂度 O ( 1 ) O(1) O(1)
