r********t
发帖数: 395 | 1 在这个网页里：http://www.careercup.com/question?id=266699
He gave me an array of Integers, each integer allows me to make at max its
value jumps. If i am at zero, i'm stuck i cannot move forword. He asked me
to find the least selection to reach end of the array.
ex: 1 3 5 8 9 2 6 7 6 8 9
initially at one i have only make one jump to 3, from 3 i can jump either 1
step 0r 2 steps 0r 3 steps.
my solution is 1 to 3 to 8, 3 selection and i am done.
Device an algo for this
有一个答案用到动态规划：
It's a dynamic program |
k*k
发帖数: 49 | 2 this should work... O(n * (n k)) where k is the range of elements. if we
only check k from 1 to s such as that s + i <= n then, the complexity
becomes n^3.....
not sure this is the most efficient....
#include
int jump(int* arr, int n){
int idx[n];
int edge[n];
int i = 0;
int j = 0;
idx[0] = 0;
for(i=1; i
int min = i;
int minidx = -1;
for(j=i-1; j>=0; j--){
int k = 0;
for(k=1; k<=arr[j]; k++){
if (arr[j]!=-1 && k+j==i){
if (idx |
b***e
发帖数: 1419 | 3 这个为什么要DP? 直接贪心不就行了? 每次找范围内下次可以跳的最远的. 复杂度是O(n).
its
asked me
either 1
【在 r********t 的大作中提到】
: 在这个网页里：http://www.careercup.com/question?id=266699
: He gave me an array of Integers, each integer allows me to make at max its
: value jumps. If i am at zero, i'm stuck i cannot move forword. He asked me
: to find the least selection to reach end of the array.
: ex: 1 3 5 8 9 2 6 7 6 8 9
: initially at one i have only make one jump to 3, from 3 i can jump either 1
: step 0r 2 steps 0r 3 steps.
: my solution is 1 to 3 to 8, 3 selection and i am done.
: Device an algo for this
: 有一个答案用到动态规划：
|
g*******y
发帖数: 1930 | 4 this is right
greedy will work, just compute another array
b[i] = i+a[i];
code如下：
int jump_count=0;
int low=0,high=0;
while(high
jump_count++;
int max=0;
for(int i=low;i<=high;i++) max = (b[i]>max)?b[i]:max;
if(max==high) throw runtime_error("unreachable");
low=high+1;
high=max;
}
return jump_count;
O(n).
【在 b***e 的大作中提到】
: 这个为什么要DP? 直接贪心不就行了? 每次找范围内下次可以跳的最远的. 复杂度是O(n).
:
: its
: asked me
: either 1
|
c*****y
发帖数: 90 | 5 Good.
【在 g*******y 的大作中提到】
: this is right
: greedy will work, just compute another array
: b[i] = i+a[i];
: code如下：
: int jump_count=0;
: int low=0,high=0;
: while(high: jump_count++;
: int max=0;
: for(int i=low;i<=high;i++) max = (b[i]>max)?b[i]:max;
|
