LeetCode - Jump Game II

发布时间:2014-10-22 12:11:29编辑: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 应用性能调试

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款