c*******u
发帖数: 47 | 1 贴了好几个方法，包括官方的答案，large data都超时。 |
l*******b
发帖数: 2586 | 2 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;
} |
c********t
发帖数: 5706 | 3 DP?
【在 c*******u 的大作中提到】
: 贴了好几个方法，包括官方的答案，large data都超时。
|
f*******t
发帖数: 7549 | |
j*****y
发帖数: 1071 | 5 BFS 的复杂度是 O(V + E)
jump game 里面的 E 差不多是 V^2 ， 所以 BFS的复杂度应该是 O(n^2)
【在 f*******t 的大作中提到】
: BFS，O(n)复杂度
|
w****a
发帖数: 710 | 6 用greedy能O(n)，用DP达不到O(n)
研究了三种DP的办法，有一种能四十多毫秒过大集合，有一种超时，一种要一千多毫秒
greedy的解jump game是最好的 |
j*****y
发帖数: 1071 | 7 怎么greedy 阿？ 多谢 :)
【在 w****a 的大作中提到】
: 用greedy能O(n)，用DP达不到O(n)
: 研究了三种DP的办法，有一种能四十多毫秒过大集合，有一种超时，一种要一千多毫秒
: greedy的解jump game是最好的
|
h**u
发帖数: 35 | 8 BFS is OK, but traverse from the farthest kid first when visiting a node
class Solution {
public:
int jump(int A[], int n)
{
if ( !A || n <=1)
return 0;
queue Q;
vector min_jump(n, -1);
Q.push(0);
min_jump[0] = 0;
while (!Q.empty()) {
int cur = Q.front();
Q.pop();
if ( A[cur] + cur >= n - 1)
return min_jump[cur] + 1;
for (int i=A[cur]; i>=1; i--) // Traverse from the farthest
{
if ( min_jump[i+cur] == -1 )
{
min_jump[i+cur] = min_jump[cur] + 1;
Q.push (i+cur);
}
}
}
return -1;
}
}; |
f*******t
发帖数: 7549 | 9 这题greedy是错的
【在 w****a 的大作中提到】
: 用greedy能O(n)，用DP达不到O(n)
: 研究了三种DP的办法，有一种能四十多毫秒过大集合，有一种超时，一种要一千多毫秒
: greedy的解jump game是最好的
|
c********t
发帖数: 5706 | 10 greedy应该没问题，参考菜鸟的codes.
【在 f*******t 的大作中提到】
: 这题greedy是错的
|
|
|
f*******t
发帖数: 7549 | 11 那个就是BFS呀
【在 c********t 的大作中提到】
: greedy应该没问题，参考菜鸟的codes.
|
j*****y
发帖数: 1071 | 12 好厉害的 linear time code
【在 l*******b 的大作中提到】
: 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;
: }
|
s****0
发帖数: 117 | 13 先贴我的，再看大家的。
public class Solution {
public int jump(int[] jmp) {
int n = jmp.length;
int canReach[] = new int[n];
for (int i = 1; i < n; i++) {
canReach[i] = Integer.MAX_VALUE;
}
canReach[0] = 0;
int head = 0;
for (int i = 0; i < n; i++) {
if (canReach[i] > n)
continue;
for (int j = Math.max(i, head) + 1; (j <= i + jmp[i]) && (j < n)
; j++) {
canReach[j] = Math.min(canReach[j], canReach[i] + 1);
if (j > head)
head = j;
}
}
return canReach[n - 1];
}
} |
c********t
发帖数: 5706 | 14 难道不是bfs+greedy?
我承认确实不太懂greedy真正的含义，看见用了max,觉得就是greedy吧?
我觉得htyu的codes是纯BFS. 不是吗？
【在 f*******t 的大作中提到】
: 那个就是BFS呀
|
f*******t
发帖数: 7549 | 15 这题早有人讨论过
http://www.mitbbs.com/article_t/JobHunting/32076261.html
BFS的原理是，假设当前一步所在范围是[i,j] （起始时i=j=0），下一步的范围就是[j
+1, max(k+A[k]) (i<=k<=j)。如果max的值大于last index，则说明当前这一步是需要
的最少步数。
【在 c********t 的大作中提到】
: 难道不是bfs+greedy?
: 我承认确实不太懂greedy真正的含义，看见用了max,觉得就是greedy吧?
: 我觉得htyu的codes是纯BFS. 不是吗？
|
