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.
算法1:暴力解法,注意A[0] = 0的边界条件.该解法O(n^2),大数据超时了
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class
Solution {
public
:
bool
canJump(
int
A[],
int
n) {
if
(n == 1)
return
true
;
else
if
(A[0] == 0)
return
false
;
bool
canArrive[n];
memset
(canArrive, 0,
sizeof
(canArrive));
canArrive[0] =
true
;
for
(
int
i = 0; i < n; i++)
{
if
(canArrive[i] ==
false
)
continue
;
int
farest = min(i + A[i], n - 1);
for
(
int
j = i + 1; j <= farest; j++)
canArrive[j] =
true
;
if
(canArrive[n-1])
return
true
;
}
return
canArrive[n-1];
}
};
|
算法2:优化解法，只需要顺序扫描数组，记录下能够到达的最远位置
|
1
2
3
4
5
6
7
8
9
|
class
Solution {
public
:
bool
canJump(
int
A[],
int
n) {
int
canArrive = 0;
//当前能到达的最远位置
for
(
int
i = 0; i <= canArrive && canArrive < n-1; i++)
if
(i + A[i] > canArrive)canArrive = i + A[i];
return
canArrive >= n-1;
}
};
|
Jump Game II
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, then3 steps to the last index.)
算法3：在上述算法1的基础上（其实是动态规划，minjumps[i] = min{minjumps[k] + 1},k<i 且 i+A[k]>=i ) 本文地址
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class
Solution {
public
:
int
jump(
int
A[],
int
n) {
vector<
int
> minjumps(n, INT_MAX);
minjumps[0] = 0;
for
(
int
i = 0; i < n; i++)
{
int
farest = min(i + A[i], n - 1);
for
(
int
j = i + 1; j <= farest; j++)
if
(minjumps[j] > minjumps[i] + 1)
minjumps[j] = minjumps[i] + 1;
}
return
minjumps[n-1];
}
};
|
算法4：在上述算法2的基础上（具体解释可参考http://www.cnblogs.com/lichen782/p/leetcode_Jump_Game_II.html）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class
Solution {
public
:
int
jump(
int
A[],
int
n) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int
canArrive = 0, res = 0, lastCanArrive = 0;
for
(
int
i = 0; i < n; i++)
{
if
(i > lastCanArrive)
{
res++;
lastCanArrive = canArrive;
}
if
(i + A[i] > canArrive)
canArrive = i + A[i];
}
return
res;
}
};
|
稍微改进一下，只要canArrive >= n-1 ,就可以结束循环，此时返回值是res+1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class
Solution {
public
:
int
jump(
int
A[],
int
n) {
// Note: The Solution object is instantiated only once and is reused by each test case.
if
(n == 1)
return
0;
int
canArrive = 0, res = 0, lastCanArrive = 0;
for
(
int
i = 0; canArrive < n-1; i++)
if
(i + A[i] > canArrive)
{
if
(i > lastCanArrive)
{
res++;
lastCanArrive = canArrive;
}
canArrive = i + A[i];
}
return
res+1;
}
};
|
算法5：从最后一个开始，找到第一个能到最后的，再往前找第一个能到新的位置的，直到第0位（参考http://www.laurashawn.net/?p=10885）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class
Solution {
public
:
int
jump(
int
A[],
int
n) {
int
i=n-1;
int
step=0;
while
(i>0){
for
(
int
j=0;j<i;j++){
if
(A[j]+j>=i){
step++;
i=j;
break
;
}
}
}
return
step;
}
};
|
