问两道leetcode上的jump game 题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问两道leetcode上的jump game 题

问两道leetcode上的jump game 题# JobHunting - 待字闺中

f*m2012-04-30 07:04

1 楼

（1）Jump Game：
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.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
不知道我下面的解法对不对？用了DP，用f存储以前的计算结果。
bool jump(vector& A, int n, vector f){
if (n == 0){
f[0] = true;
return true;
}
if (f[n] != -1)
return f[n];
bool temp = false;
for (int i = 0; i < n; i++){
if (n-i <= A[i])
temp = temp || jump(A, i, f);
}
f[n] = temp;
return f[n];
}
（2） Jump game 2:
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.)
我的做法：
int minjump(vector& a, int n, vector& f){
if (n == 0){
f[n] = 0;
return f[n];
}
if (f[n] != -1)
return f[n];
int minj = INT_MAX;
for (int i = 0; i < n; i++){
if (n-i <= a[i]){
if (minjump(a, i, f)+1 < minj)
minj = minjump(a, i, f)+1;
}
}
f[n] = minj;
return f[n];
}

c*p2012-04-30 07:04

2 楼

DP是对的。

the

【在 f*********m 的大作中提到】

: （1）Jump Game：
: 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.
: Determine if you are able to reach the last index.
: For example:
: A = [2,3,1,1,4], return true.
: A = [3,2,1,0,4], return false.
: 不知道我下面的解法对不对？用了DP，用f存储以前的计算结果。

n*k2012-04-30 07:04

3 楼

对呀,还可以更好
On时间，O1空间
因为你如果能走到第五步，不管怎么样你都能走到第k步，k<5
算法是用一个循环变量i，用一个变量k表示目前找到的最远的步数。
i=0
k=0
i每次增1，如果在第i步发现能走的比k远，更新k；如果发现i>k，失败；如果发现i==n
,成功

c*p2012-04-30 07:04

4 楼

这题有时候会问最少需要几步

=n

【在 n********k 的大作中提到】

: 对呀,还可以更好
: On时间，O1空间
: 因为你如果能走到第五步，不管怎么样你都能走到第k步，k<5
: 算法是用一个循环变量i，用一个变量k表示目前找到的最远的步数。
: i=0
: k=0
: i每次增1，如果在第i步发现能走的比k远，更新k；如果发现i>k，失败；如果发现i==n
: ,成功

s*52012-04-30 07:04

5 楼

第一个jump不用DP吧。从头scan, keeps updating the furthest position you can
go, when the furthest position is current position, then return false.
bool Jump(int a[], int size)
{
int i = 0;
int furthest = 0;
while (i{
int tmp = i+a[i];
if (tmp > furthest)
furthest = tmp;
if (furthest >= size-1)
return true;
if (furthest == i)
return false;

++i;
}
return true;
}

y*o2012-04-30 07:04

6 楼

first no need for dp at all
class Solution {
public:
bool canJump(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(n<=0)
return 1;
int maxReach=A[0];
for(int i=1;iif(maxReach>=i){
if(A[i]+i>maxReach){
maxReach=A[i]+i;
}
}else{
return 0;
}
}
return 1;
}
};

the

【在 f*********m 的大作中提到】

j*x2012-04-30 07:04

7 楼

8 bool is_reachable(const std::vector& A) {
9 int max = 0;
10 int max_pos = A.size() - 1;
11 for (int i = 0; i <= max && i <= max_pos && max < max_pos; ++i) {
12 max = std::max(max, i + A[i]);
13 }
14
15 return max >= max_pos;
16 }