LeetCode - Jump Game II

发布时间:2016-12-7 18:29:28 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"LeetCode - Jump Game II",主要涉及到LeetCode - Jump Game II方面的内容,对于LeetCode - Jump Game II感兴趣的同学可以参考一下。

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. For example: Given array A = [2,3,1,1,4] The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.) 动态规划的方法(大数据TLE) class Solution { public: int jump(int A[], int n) { if(n<2){ return 0; } vector<int> len(n,0); for(int i= n-2;i>=0;i--){ len[i]=n-i-1; for(int j=i+1;j<=min(i+A[i],n-1);j++){ len[i]=min(len[i],len[j]+1); } } return len[0]; } };在Jump Game 题目解法的基础上稍作修改,AC class Solution { public: int jump(int A[], int n) { if(n<2){ return 0; } int len=0,counter=0,i=0; for(;i<n-1;i++){ len=max(len-1,A[i]); A[i]=len; if(len==0){ return -1; } } i=0; while(i<n-1){ i+=A[i]; counter++; } return counter; } };

上一篇:【转】用代码实现血条或力量条效果
下一篇:Android 应用性能调试

相关文章

相关评论