虚拟主机销售网站源码,网站的模板演示怎么做,工地模板图片大全,南宁市起全网络科技有限公司每次更新目标位置时#xff0c;实际上是在做一个局部的最优选择#xff0c;选择跳跃能够到达当前目标位置的最远位置。因为每次更新目标位置时#xff0c;都是基于当前能跳跃到的最远位置#xff0c;因此最终的结果是全局最优的。
题目 从前往后遍历#xff0c;更新可以到…每次更新目标位置时实际上是在做一个局部的最优选择选择跳跃能够到达当前目标位置的最远位置。因为每次更新目标位置时都是基于当前能跳跃到的最远位置因此最终的结果是全局最优的。
题目 从前往后遍历更新可以到达的最远坐标当最远坐标大于等于最后一个坐标即可到达一旦当前坐标比最远坐标大即更新的最远坐标达不到遍历的位置坐标。
时间复杂度 O(n)空间复杂度O(1)。
class Solution {public boolean canJump(int[] nums) {//当前能到达的最远坐标int mx0;for (int i 0; i nums.length; i) {if(imx)return false;//若当前坐标大于最远坐标说明不能到达当前坐标直接返回//若当前小于最远坐标说明可以到达mxMath.max(mx,inums[i]);//使用当前坐标的移动范围 更新能到达的最远坐标}return true;}
}
从后往前遍历 设定一个指针为目标位置当前位置能通过跳跃到达当前目标位置就更新目标位置为当前位置最终判断是否能回到起点。
时间复杂度 O(n)空间复杂度O(1)。
class Solution {public boolean canJump(int[] nums) {int last nums.length - 1; // 目标位置是数组的最后一个位置for (int i nums.length - 2; i 0; i--) {if (i nums[i] last) {last i; // 如果当前位置能跳跃到目标位置更新目标位置}}return last 0; // 如果最终目标位置是第一个位置说明可以从起点到达终点}
}这题仔细一看数组中的每个元素都大于等于一时一步一步走再慢也可以走到而此时数组中的零可以看作一个坑越过了便可到达。
