网站建设贰金手指下拉,网站什么语言好,食品网站模板下载,杭州公司排名贪心算法#xff0c;存下每一步的最远#xff0c;去达到全局的最小跳跃次数。
题目 从题中要达到最少次数#xff0c;肯定是每一步尽可能走远一点。但注意j被限制了范围#xff0c;这种不用想每一步遍历时肯定选最大的num[i]#xff0c;但要注意#xff0c;题中是可以到…贪心算法存下每一步的最远去达到全局的最小跳跃次数。
题目 从题中要达到最少次数肯定是每一步尽可能走远一点。但注意j被限制了范围这种不用想每一步遍历时肯定选最大的num[i]但要注意题中是可以到达不是刚好到达因此最后一步只要大于最后一个数都是可以的。从第一个数开始遍历每一步贪心去选最远的距离然后每个数都存下一个可达到的最远距离便于更新因为贪心每一次都是基于当前数的最优并不是全局最优。
时间复杂度 O(n)空间复杂度 O(1)。
class Solution {public int jump(int[] nums) {int step0,end0,furthest0;for(int i0; inums.length-1;i){ furthest Math.max(furthest, inums[i]); //dp每个i记录每个位置能达到的最远距离if(iend){ //i遍历到上个起跳点能到的最远距离end furthest; //更新到下一步要跳到的位置注意这里跳的最远距离由i前面的数贪心选出来的step; //跳往下一步因此最后一个数不用遍历}}return step;}
}
动态规划是存一个要维护状态的dp数组每次的状态由上几个状态更新得到这题用dp会很慢。而贪心策略在于每一步都存下最优状态便于后续的更新。
