重庆在线课程开放平台,内蒙古seo公司,网站建设邀标比选,商业设计网站推荐想了一个晚上#xff0c;第一个思路是用动态规划#xff0c;记录走到每一个节点需要跳动的最小步数#xff0c;大致方法是每走到一个节点就遍历一下前面的全部节点#xff0c;看看哪个节点可以一部跳到该节点#xff0c;然后从中选取跳跃步数最小的节点#xff0c;最后输…
想了一个晚上第一个思路是用动态规划记录走到每一个节点需要跳动的最小步数大致方法是每走到一个节点就遍历一下前面的全部节点看看哪个节点可以一部跳到该节点然后从中选取跳跃步数最小的节点最后输出最后一个节点的跳跃步数即可。
当时想到这个方法的时候就有会时间超限的直觉…结果还真时间超限了…………改了一下通过了但运行时间击败5%的代码………………………………
class Solution {
public:int jump(vectorint nums) {int result0;int location0;int b[nums.size()];b[0]0;for(int i1;inums.size();i){int m100000;for(int j0;ji;j){if(nums[j]i-jb[j]1m) mb[j]1;}b[i]m;}return b[nums.size()-1];}
};
然后看了一眼解析发现新的思路依次算出运行n步能到达的最远节点然后取那个最远能到最后一个节点的步数。
用这种思路做了一下然后时间复杂度击败70%代码………………
class Solution {
public:int jump(vectorint nums) {int step0;int start0;int end0;while(endnums.size()-1){int maxx0;for(int istart;iend1;i){maxxmax(maxx,inums[i]);}startend;endmaxx;step;}return step;}
};
