S****h
发帖数: 115 | 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.)
我就按照最短路径的解法来做，初始化所有mj[A.length](minimum jump)为Integer.
MAX_VALUE, 然后mj[0] = 0; 后面利用PriorityQueue每次找最短path那个点，Update
所有相邻点。直到找到最后一点，找不到则返回-1. However，测试案例judge small都
过了，但是judge large超时... 求建议！
//leetcode大神是不是在啊？
==================================================== |
l*********8
发帖数: 4642 | 2 以前gloomyturkey贴过一个O(n)的程序。 |
h****e
发帖数: 928 | |
S****h
发帖数: 115 | |
l*********8
发帖数: 4642 | 5 写了个递归的玩，呵呵
int jump(int A[], int n, int reach=1)
{
if (n<=reach) return 0;
int nextReach=reach;
for (int i=0; i
nextReach=max(nextReach, A[i]+i+1);
return 1+jump(A+reach, n-reach, nextReach-reach);
} |
q***y
发帖数: 236 | 6 我的dp方法。过了online judge。请大家帮忙看看复杂度多少？
int jump(int A[], int n) {
vector steps(n);
steps[n-1] = 0;
for (int i=n-2; i>=0; --i) {
if (A[i]==0) steps[i] = -1; // unable to reach
else if (A[i]>=n-i-1) steps[i] = 1;
else {
int msp = n-i-1;
for (int j=A[i]; j>0; --j) {
if (steps[i+j]>-1 && steps[i+j]
if (msp==1) break;
}
steps[i] = msp+1;
}
}
return steps[0];
} |
l*********8
发帖数: 4642 | 7 O(n^2)时间， O(n)空间
【在 q***y 的大作中提到】
: 我的dp方法。过了online judge。请大家帮忙看看复杂度多少？
: int jump(int A[], int n) {
: vector steps(n);
: steps[n-1] = 0;
: for (int i=n-2; i>=0; --i) {
: if (A[i]==0) steps[i] = -1; // unable to reach
: else if (A[i]>=n-i-1) steps[i] = 1;
: else {
: int msp = n-i-1;
: for (int j=A[i]; j>0; --j) {
|
S****h
发帖数: 115 | 8 嗯，看来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;
}
return jumpCount;
}
【在 h****e 的大作中提到】
: 是的，用greedy算法(见火鸡的code)：
: http://www.mitbbs.com/article_t/JobHunting/32076261.html
: 另外一道相似的题目thrust是5行code写出的:
: http://www.mitbbs.com/article_t/JobHunting/32073485.html
|
b******v
发帖数: 1493 | 9 火鸡好牛
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 h****e 的大作中提到】
: 是的，用greedy算法(见火鸡的code)：
: http://www.mitbbs.com/article_t/JobHunting/32076261.html
: 另外一道相似的题目thrust是5行code写出的:
: http://www.mitbbs.com/article_t/JobHunting/32073485.html
|
p*****o
发帖数: 1285 | 10 今天写了一个O(N^2)的，一个O(kn)的，k是从各点开始最短路径里的最大值。kn的轻松
过关，n^2的本来过不了，加了个dirty hack就过了。分别如下：
// O(n^2)
class Solution {
public:
int jump(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector cost(n, 0x7fffffff);
cost[n-1] = 0;
for (int i=n-2; i>=0; --i){
int mj = 0x7fffffff;
for (int j = min(n-1, i + A[i]); j > i; --j){
if (cost[j] < mj) mj = cost[j];
if (mj <= 1) break; // dirty hack which improve the
algorithm amazingly well
}
if (mj != 0x7fffffff) cost[i] = mj+1;
}
return cost[0];
}
}
// O(kn), k is the max of min jumps from each position to the end.
class Solution {
public:
int jump(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector cost_idx;
cost_idx.push_back(n-1);
int cost = 0;
for (int i=n-2; i>=0; --i) if (A[i] != 0){
cost = -1;
int j=0;
while (j i+A[i]) ++j;
if (j
cost = j+1;
if (cost < cost_idx.size()) cost_idx[cost] = i;
else cost_idx.push_back(i);
}
}
return cost;
}
};
the
from
【在 S****h 的大作中提到】
: 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.)
: 我就按照最短路径的解法来做，初始化所有mj[A.length](minimum jump)为Integer.
|
g**x
发帖数: 373 | 11 另一种 O(N) 的解法：
http://slientcode.blogspot.com/2012/05/jump-game-2.html
【在 p*****o 的大作中提到】
: 今天写了一个O(N^2)的，一个O(kn)的，k是从各点开始最短路径里的最大值。kn的轻松
: 过关，n^2的本来过不了，加了个dirty hack就过了。分别如下：
: // O(n^2)
: class Solution {
: public:
: int jump(int A[], int n) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: vector cost(n, 0x7fffffff);
: cost[n-1] = 0;
|
