leetcode https://oj.leetcode.com/problems/jump-game-ii/
6121 ワード
1.タイムアウト、非効率
実際には判断する必要はありません.カバー領域を求めると、現在最も長い+1に違いありません.
1 public class Solution {
2 public int jump(int[] A) {
3 int len=A.length;
4 int d[]=new int[len];
5 d[0]=0;
6
7
8 for(int i=1;i<len;i++)
9 {
10 d[i]=1;
11 int j;
12 for(j=1;j+i<len&&j<=A[j];j++)
13 {
14 d[i+j]=Math.max(d[i]+1,d[j+i]);
15 }
16 if(j+i==len) return d[len-1];
17
18 }
19
20 return d[len-1];
21
22
23
24
25
26
27 }
28 }実際には判断する必要はありません.カバー領域を求めると、現在最も長い+1に違いありません.
public class Solution {
public int jump(int[] A) {
int len=A.length;
int step=0;
int last=0;
int maxpost=0;
for(int i=0;i<len;i++)
{
if(i>last)
{
step++;
last=maxpost;
}
maxpost=Math.max(i+A[i],maxpost);
}
return step;
}
}
AC
public class Solution {
public int jump(int[] A) {
int len=A.length;
int step=0;//
int last=0; //
int maxpost=0;// ， bfs ， ，bfs
for(int i=0;i<len;i++)
{
if(i>last)
{
step++;
last=maxpost;
}
maxpost=Math.max(i+A[i],maxpost);
}
return step;
}
}