s******e
发帖数: 108 | 1 from front to back
O(n).
each time select the max reachable postion to jump.
public static int jump(int [] A) {
if(A.length<=1)
return 0;
int jumpcount =0;
int i =0;
int currentmaxEnd =0;
while(i
currentmaxEnd = A[i]+i;
if(A[i]>0)
jumpcount++;
else
... 阅读全帖 |
|
s******e
发帖数: 108 | 2 from front to back
O(n).
each time select the max reachable postion to jump.
public static int jump(int [] A) {
if(A.length<=1)
return 0;
int jumpcount =0;
int i =0;
int currentmaxEnd =0;
while(i
currentmaxEnd = A[i]+i;
if(A[i]>0)
jumpcount++;
else
... 阅读全帖 |
|
s******e
发帖数: 108 | 3 a more concise version
public static int jump (int [] A) {
int jumpcount =0;
int startPos =0;
int max = 0;
int newmax = 0;
while(max
jumpcount++;
for(int i=startPos; i<=max;i++){
newmax = Math.max(newmax, A[i]+i);
}
startPos = max+1;
... 阅读全帖 |
|
s******e
发帖数: 108 | 4 a more concise version
public static int jump (int [] A) {
int jumpcount =0;
int startPos =0;
int max = 0;
int newmax = 0;
while(max
jumpcount++;
for(int i=startPos; i<=max;i++){
newmax = Math.max(newmax, A[i]+i);
}
startPos = max+1;
... 阅读全帖 |
|
S****h
发帖数: 115 | 5 嗯，看来greedy确实是最优解法O(n),贴个code:
public int jump(int[] A) {
int jumpCount = 0;
int index = 0;
int limit = 0;
while (limit < A.length - 1) {
jumpCount++;
int temp = limit;
for (int i = index; i <= limit; i++) {
if (A[i] + i > temp)
temp = A[i] + i;
}
// can not progress
if (limit == temp)
return -1;
// progress
index = limit + 1;
limit = temp;
... 阅读全帖 |
|
