h******i
发帖数: 30 | 1 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.)
我用greedy algorithm解的 但是超时了。
int jump(int A[], int n)
{
if(n<=1)
return 0;
int ret = 0;
int i = 0;
int index = -1;
while (i < n-1)
{
int maxDis = 0;
for(int j = 0; j<=A[i];++j)
{
if(j+A[i+j]>maxDis)
{
maxDis=j+A[i+j];
index = j;
}
}
i+=index;
++ret;
}
return ret;
} |
g*********e
发帖数: 14401 | |
p*****2
发帖数: 21240 | |
s******n
发帖数: 3946 | 4 恩，从后往前dp应该可以
【在 g*********e 的大作中提到】
: 我前几天做出过 从后往前dp O(n）
|
s******e
发帖数: 108 | 5 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
return 0;
if(currentmaxEnd>=A.length-1 )
return jumpcount;
int max = 0;
for(int j=i+1;j<=currentmaxEnd;j++){
if(A[j]+j >= max) {
max = A[j]+j;
i = j;
}
}
}
return jumpcount;
}
the
from
【在 h******i 的大作中提到】
: 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.)
: 我用greedy algorithm解的 但是超时了。
|
g**********y
发帖数: 14569 | 6 前天不就讨论这个题，thrust用5行code就出来了。那个解法就是标准答案。 |
s******n
发帖数: 3946 | 7 在哪里? 去学习一下
【在 g**********y 的大作中提到】
: 前天不就讨论这个题，thrust用5行code就出来了。那个解法就是标准答案。
|
g**********y
发帖数: 14569 | |
s******n
发帖数: 3946 | 9 题目要求不一样? 一个要求判断能否走到最后一步，这个是走到最后一步的最少jump
【在 g**********y 的大作中提到】
: http://www.mitbbs.com/article_t/JobHunting/32073485.html
|
p*****2
发帖数: 21240 | 10 是
题目要求不一样? 一个要求判断能否走到最后一步，这个是走到最后一步的最少jump
★ Sent from iPhone App: iReader Mitbbs Lite 7.51
【在 s******n 的大作中提到】
: 题目要求不一样? 一个要求判断能否走到最后一步，这个是走到最后一步的最少jump
|
|
|
s******e
发帖数: 108 | 11 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;
if(newmax<=max)
return -1;
max=newmax;
}
return jumpcount;
}
【在 s******e 的大作中提到】
: 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
|
h*****f
发帖数: 248 | 12 smalleye's solution is better...
in case anyone wants a dp version (from front to back):
int compute(int a[], int length) {
int b[length];
int max = std::numeric_limits::max();
for (int i = 0; i < length; i++) b[i] = -1; // not reachable
b[0] = 0; // first one is alway reachable
for (int i = 0; i < length; i++) {
if (b[i] >= 0) {
// only try if the current index is reachable
for (int j = i + 1; j <= i + a[i] && j < length; j++) {
if (1 + b[i] < b[j] || -1 == b[j]) {
b[j] = 1 + b[i];
if (b[j] < max && j == length - 1) max = b[j];
}
}
}
}
if (std::numeric_limits::max() == max) return -1;
return max;
}
O(n^2) |
e***s
发帖数: 799 | 13 这题DP O(n^2)好像是逃不了了，不知道有没有大牛有更牛B解法。
【在 h*****f 的大作中提到】
: smalleye's solution is better...
: in case anyone wants a dp version (from front to back):
: int compute(int a[], int length) {
: int b[length];
: int max = std::numeric_limits::max();
: for (int i = 0; i < length; i++) b[i] = -1; // not reachable
: b[0] = 0; // first one is alway reachable
: for (int i = 0; i < length; i++) {
: if (b[i] >= 0) {
: // only try if the current index is reachable
|
l****c
发帖数: 782 | 14 lz,
你的方法有没有可能有一次最远跳的地方却是一个0啊，
那样greedy不work了啊, 0的时候如何操作是不是也要写下呢
the
from
【在 h******i 的大作中提到】
: 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.)
: 我用greedy algorithm解的 但是超时了。
|
e***s
发帖数: 799 | 15 public static int JumpGameII(int[] A)
{
if (A.Length <= 1)
return 0;
int[] MinJumps = new int[A.Length];
MinJumps[0] = 0;
for (int i = 1; i < A.Length; i++)
{
int Min = Int16.MaxValue;
for (int j = 0; j < i; j++)
{
if (MinJumps[j] >= Min)
continue;
if (A[j] >= i - j)
Min = Math.Min(Min, MinJumps[j] + 1);
}
MinJumps[i] = Min;
}
return MinJumps[MinJumps.Length - 1];
} |
h*****3
发帖数: 1391 | |
C*******n
发帖数: 49 | 17 Think like this: if A[i] = x, then A[i] has an edge (with weight all equal
to 1) to all A[i+1...i+x].
Then the problem is just a BFS to count the shortest path from A[0] to A[n-
1].
public int jump(int[] A) {
int count = 0;
int start=0, end=0, newend;
while (end < A.length-1){
count++;
newend = 0;
for (int i=start; i<=end; i++)
newend = i+A[i]>newend ? (i+A[i]) : newend;
start = end+1;
end = newend;
}
return count;h
} |
D**********d
发帖数: 849 | 18 这个不是 shortest path algorithm 吗？而且是很特殊的，
复杂度应是 O(c*N), where c = array_max_number,以下就是一算法
让 S[n] 表示到达每数的最小步数，
for(i = 1; i < LenArray; ++i){
S[i] = INF;
}
for(S[0]=0,i=1; i < LenArray; ++i){
for(j=0; j < min(Array[i],LenArray); ++j){
S[i+j] = min(S[i+j],S[i]+1);
}
}
最后的答案是 S[LenArray-1] |
C***U
发帖数: 2406 | 19 你这个想法不错！！
jump game 1和2都能用这个办法解决 都变成tree transverse了
用bfs就可以了吧
而且是O(n)时间的
【在 D**********d 的大作中提到】
: 这个不是 shortest path algorithm 吗？而且是很特殊的，
: 复杂度应是 O(c*N), where c = array_max_number,以下就是一算法
: 让 S[n] 表示到达每数的最小步数，
: for(i = 1; i < LenArray; ++i){
: S[i] = INF;
: }
: for(S[0]=0,i=1; i < LenArray; ++i){
: for(j=0; j < min(Array[i],LenArray); ++j){
: S[i+j] = min(S[i+j],S[i]+1);
: }
|
h******i
发帖数: 30 | 20 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.)
我用greedy algorithm解的 但是超时了。
int jump(int A[], int n)
{
if(n<=1)
return 0;
int ret = 0;
int i = 0;
int index = -1;
while (i < n-1)
{
int maxDis = 0;
for(int j = 0; j<=A[i];++j)
{
if(j+A[i+j]>maxDis)
{
maxDis=j+A[i+j];
index = j;
}
}
i+=index;
++ret;
}
return ret;
} |
|
|
g*********e
发帖数: 14401 | |
p*****2
发帖数: 21240 | |
s******n
发帖数: 3946 | 23 恩，从后往前dp应该可以
【在 g*********e 的大作中提到】
: 我前几天做出过 从后往前dp O(n）
|
s******e
发帖数: 108 | 24 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
return 0;
if(currentmaxEnd>=A.length-1 )
return jumpcount;
int max = 0;
for(int j=i+1;j<=currentmaxEnd;j++){
if(A[j]+j >= max) {
max = A[j]+j;
i = j;
}
}
}
return jumpcount;
}
the
from
【在 h******i 的大作中提到】
: 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.)
: 我用greedy algorithm解的 但是超时了。
|
g**********y
发帖数: 14569 | 25 前天不就讨论这个题，thrust用5行code就出来了。那个解法就是标准答案。 |
s******n
发帖数: 3946 | 26 在哪里? 去学习一下
【在 g**********y 的大作中提到】
: 前天不就讨论这个题，thrust用5行code就出来了。那个解法就是标准答案。
|
g**********y
发帖数: 14569 | |
s******n
发帖数: 3946 | 28 题目要求不一样? 一个要求判断能否走到最后一步，这个是走到最后一步的最少jump
【在 g**********y 的大作中提到】
: http://www.mitbbs.com/article_t/JobHunting/32073485.html
|
p*****2
发帖数: 21240 | 29 是
题目要求不一样? 一个要求判断能否走到最后一步，这个是走到最后一步的最少jump
★ Sent from iPhone App: iReader Mitbbs Lite 7.51
【在 s******n 的大作中提到】
: 题目要求不一样? 一个要求判断能否走到最后一步，这个是走到最后一步的最少jump
|
s******e
发帖数: 108 | 30 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;
if(newmax<=max)
return -1;
max=newmax;
}
return jumpcount;
}
【在 s******e 的大作中提到】
: 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
|
|
|
h*****f
发帖数: 248 | 31 smalleye's solution is better...
in case anyone wants a dp version (from front to back):
int compute(int a[], int length) {
int b[length];
int max = std::numeric_limits::max();
for (int i = 0; i < length; i++) b[i] = -1; // not reachable
b[0] = 0; // first one is alway reachable
for (int i = 0; i < length; i++) {
if (b[i] >= 0) {
// only try if the current index is reachable
for (int j = i + 1; j <= i + a[i] && j < length; j++) {
if (1 + b[i] < b[j] || -1 == b[j]) {
b[j] = 1 + b[i];
if (b[j] < max && j == length - 1) max = b[j];
}
}
}
}
if (std::numeric_limits::max() == max) return -1;
return max;
}
O(n^2) |
e***s
发帖数: 799 | 32 这题DP O(n^2)好像是逃不了了，不知道有没有大牛有更牛B解法。
【在 h*****f 的大作中提到】
: smalleye's solution is better...
: in case anyone wants a dp version (from front to back):
: int compute(int a[], int length) {
: int b[length];
: int max = std::numeric_limits::max();
: for (int i = 0; i < length; i++) b[i] = -1; // not reachable
: b[0] = 0; // first one is alway reachable
: for (int i = 0; i < length; i++) {
: if (b[i] >= 0) {
: // only try if the current index is reachable
|
l****c
发帖数: 782 | 33 lz,
你的方法有没有可能有一次最远跳的地方却是一个0啊，
那样greedy不work了啊, 0的时候如何操作是不是也要写下呢
the
from
【在 h******i 的大作中提到】
: 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.)
: 我用greedy algorithm解的 但是超时了。
|
e***s
发帖数: 799 | 34 public static int JumpGameII(int[] A)
{
if (A.Length <= 1)
return 0;
int[] MinJumps = new int[A.Length];
MinJumps[0] = 0;
for (int i = 1; i < A.Length; i++)
{
int Min = Int16.MaxValue;
for (int j = 0; j < i; j++)
{
if (MinJumps[j] >= Min)
continue;
if (A[j] >= i - j)
Min = Math.Min(Min, MinJumps[j] + 1);
}
MinJumps[i] = Min;
}
return MinJumps[MinJumps.Length - 1];
} |
h*****3
发帖数: 1391 | |
C*******n
发帖数: 49 | 36 Think like this: if A[i] = x, then A[i] has an edge (with weight all equal
to 1) to all A[i+1...i+x].
Then the problem is just a BFS to count the shortest path from A[0] to A[n-
1].
public int jump(int[] A) {
int count = 0;
int start=0, end=0, newend;
while (end < A.length-1){
count++;
newend = 0;
for (int i=start; i<=end; i++)
newend = i+A[i]>newend ? (i+A[i]) : newend;
start = end+1;
end = newend;
}
return count;h
} |
D**********d
发帖数: 849 | 37 这个不是 shortest path algorithm 吗？而且是很特殊的，
复杂度应是 O(c*N), where c = array_max_number,以下就是一算法
让 S[n] 表示到达每数的最小步数，
for(i = 1; i < LenArray; ++i){
S[i] = INF;
}
for(S[0]=0,i=1; i < LenArray; ++i){
for(j=0; j < min(Array[i],LenArray); ++j){
S[i+j] = min(S[i+j],S[i]+1);
}
}
最后的答案是 S[LenArray-1] |
C***U
发帖数: 2406 | 38 你这个想法不错！！
jump game 1和2都能用这个办法解决 都变成tree transverse了
用bfs就可以了吧
而且是O(n)时间的
【在 D**********d 的大作中提到】
: 这个不是 shortest path algorithm 吗？而且是很特殊的，
: 复杂度应是 O(c*N), where c = array_max_number,以下就是一算法
: 让 S[n] 表示到达每数的最小步数，
: for(i = 1; i < LenArray; ++i){
: S[i] = INF;
: }
: for(S[0]=0,i=1; i < LenArray; ++i){
: for(j=0; j < min(Array[i],LenArray); ++j){
: S[i+j] = min(S[i+j],S[i]+1);
: }
|
I*********7
发帖数: 125 | 39
这个方法 TLE，我开始就这么做的。结果大测试的最后一个数据是
[1800, 1799, 1798, ... 3, 2, 1, 1, 0],就是说前1800个都是最多能到 倒数第三个
数。
【在 D**********d 的大作中提到】
: 这个不是 shortest path algorithm 吗？而且是很特殊的，
: 复杂度应是 O(c*N), where c = array_max_number,以下就是一算法
: 让 S[n] 表示到达每数的最小步数，
: for(i = 1; i < LenArray; ++i){
: S[i] = INF;
: }
: for(S[0]=0,i=1; i < LenArray; ++i){
: for(j=0; j < min(Array[i],LenArray); ++j){
: S[i+j] = min(S[i+j],S[i]+1);
: }
|
b***i
发帖数: 3043 | 40 应该使用广度优先
先设from数组，储存出发的下标，初始时只有0这个下标，然后设立到过数组，逻辑，
表示以前到过这里，
然后在from里面遍历，看是否到达最后一个下标，否则每一个可能的目标如果没到过，
则存到目标数组。完成后，把目标数组作为from无限循环。
这样，用有限的存储空间和BFS完成这个任务。其中注意，超时可以这样解决，生成目
标数组的时候，把远的目标先放进去。这只是因为测试的数据都是从大到小的。
the
from
【在 h******i 的大作中提到】
: 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.)
: 我用greedy algorithm解的 但是超时了。
|
|
|
b***i
发帖数: 3043 | 41 TLE啥意思？
【在 I*********7 的大作中提到】
:
: 这个方法 TLE，我开始就这么做的。结果大测试的最后一个数据是
: [1800, 1799, 1798, ... 3, 2, 1, 1, 0],就是说前1800个都是最多能到 倒数第三个
: 数。
|
l****o
发帖数: 315 | 42 public class Solution {
public int jump(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
int curMax = 0; int nextMax = 0; int ans = 0;
for (int i = 0; i < A.length; i++) {
if (i <= curMax) {
if (A[i] + i > nextMax)
nextMax = A[i] + i;
} else {
curMax = nextMax;
ans++;
i--;
}
}
return ans;
}
} |
t**r
发帖数: 3428 | 43 这题目如果有a[i] = 0的case
很多前面的算法就不成力了把 |
T******7
发帖数: 1419 | 44 this is a clear and good idea :)
【在 b***i 的大作中提到】
: 应该使用广度优先
: 先设from数组，储存出发的下标，初始时只有0这个下标，然后设立到过数组，逻辑，
: 表示以前到过这里，
: 然后在from里面遍历，看是否到达最后一个下标，否则每一个可能的目标如果没到过，
: 则存到目标数组。完成后，把目标数组作为from无限循环。
: 这样，用有限的存储空间和BFS完成这个任务。其中注意，超时可以这样解决，生成目
: 标数组的时候，把远的目标先放进去。这只是因为测试的数据都是从大到小的。
:
: the
: from
|
T******7
发帖数: 1419 | 45 temporary load expensive?
【在 b***i 的大作中提到】
: TLE啥意思？
|
l*******b
发帖数: 2586 | 46 int jump(int A[], int n) {
int p = 0, q = 0, i = 0;
while(q < n-1) {
int m = q;
for(; p <= q; ++p)
m = max(m, p + A[p]);
if(m == q) return -1; // in case cannot reach end
q = m;
++i;
}
return i;
}
挺好做得这个，哈哈 |
h**6
发帖数: 4160 | 47 构造一个n顶点的有向图，把能到达的顶点连起来，然后用dijkstra求最短路径。 |
j*******e
发帖数: 1058 | |
l*******b
发帖数: 2586 | 49 time limit exceeded
【在 T******7 的大作中提到】
: temporary load expensive?
|
