首页 > 代码库 > Jump Game II <LeetCode>
Jump Game II <LeetCode>
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.
说明：首先该方法会超时
刚看到这道题就想到了分支限界（广度优先遍历），直接用分支限界的思想做的，结果超时了，以下是代码
1 int maxx; 2 struct node 3 { 4 int val; 5 bool k; 6 }; 7 class Solution { 8 public: 9 int jump(int A[], int n) {10 if(n==1) return 0;11 list<int> duilie;12 vector<node> temp;13 duilie.clear();14 temp.clear();15 maxx=0;16 for(int i=0;i<n;i++)17 {18 node no;19 no.val=A[i];20 no.k=true;21 temp.push_back(no);22 }23 duilie.push_back(0);24 return doit(temp,1,duilie,n,0);25 }26 27 28 int doit(vector<node> temp,int dep,list<int> duilie,int nn,int mm)29 {30 int m=0;31 for(int j=0;j<=mm;j++)32 {33 int n=duilie.front();34 duilie.pop_front();35 for(int i=1;i<=temp[n].val;i++)36 {37 if(i+n<=maxx) continue;38 else maxx=i+n;39 if(n+i<nn)40 {41 if(n+i==nn-1)42 {43 return dep;44 }45 if(temp[n+i].k)46 {47 duilie.push_back(n+i);48 m++;49 temp[n+i].k=false;50 }51 }52 else break;53 }54 }55 return doit(temp,dep+1,duilie,nn,m);56 }57 };
2：第二种思路是反过来想，要达到最后一条，倒数第二条至少应该到哪个位置，以此类推直到我们倒推到第一位时便可知最小跳数；
1 class Solution { 2 public: 3 int jump(int A[], int n) { 4 // Start typing your C/C++ solution below 5 // DO NOT write int main() function 6 int pre = 0; 7 int cur = n - 1; 8 int count = 0; 9 while(true)10 {11 if(pre == cur)12 {13 return 0;14 }15 count++;16 pre = cur;17 for(int i = n - 2; i >= 0; i--)18 {19 if(i + A[i] >= pre)20 {21 if(cur > i)22 {23 cur = i;24 }25 }26 }27 if(cur == 0)28 {29 return count;30 }31 };32 33 34 }35 };
3：第三种思路是用动态规划DP的观点来实现。DP[i]代表到达i的最小跳数，显然DP是一个递增的数组。每次循环只需要尽量找到最小的DP[k]，使其满足k+A[k]>=n。
1 class Solution { 2 public: 3 int* dp; 4 int jump(int A[], int n) { 5 if(n==0) 6 { 7 return INT_MAX; 8 } 9 dp = new int[n];10 dp[0] = 0;11 for(int i=1;i<n;i++)12 {13 dp[i] = INT_MAX;14 }15 for(int i=1;i<n;i++)16 {17 for(int j=0;j<i;j++)18 {19 if(j+A[j]>=i)20 {21 int tmp = dp[j]+1;22 if(tmp < dp[i])23 {24 dp[i] = tmp;25 break;26 }27 }28 }29 }30 31 return dp[n-1];32 }33 };
Jump Game II <LeetCode>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。