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. 不是吗?
|