由买买提看人间百态

topics

全部话题 - 话题: jumpcount
(共0页)
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;
... 阅读全帖
(共0页)