撰文 | JZ
专栏 | 九章算法
题目描述
给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
判断你是否能到达数组的最后一个位置。
样例 1
-
输入 : [2,3,1,1,4]
-
输出 : true
样例 2
-
输入 : [3,2,1,0,4]
-
输出 : false
题解
这个问题有两个方法，一个是贪心和 动态规划。
贪心方法时间复杂度为O（N）。
动态规划方法的时间复杂度为为O（n^2）。
九章参考程序
https://www. jiuzhang.com/solution/j ump-game/
1. DP1
每到一个点 i，我们扫描之前所有的点，如果之前某点j本身可达，并且与current 点可达，表示点i是可达的。
返回值：DP数组的最后一个值。
-
// DP1.
-
public
boolean
canJump1
(
int
[]
A
)
{
-
if
(
A
==
null
||
A
.
length
==
0
)
{
-
return
false
;
-
}
-
-
int
len
=
A
.
length
;
-
boolean
[]
can
=
new
boolean
[
len
];
-
can
[
0
]
=
true
;
-
-
for
(
int
i
=
1
;
i
<
len
;
i
++)
{
-
can
[
i
]
=
false
;
-
for
(
int
j
=
0
;
j
<
i
;
j
++)
{
-
// j can arrive and can jump to i.
-
if
(
can
[
j
]
&&
A
[
j
]
>=
i
-
j
)
{
-
can
[
i
]
=
true
;
-
break
;
-
}
-
}
-
}
-
-
return
can
[
len
-
1
];
-
}
2. DP2
优化的点1：既然某点可达，肯定前面的点全部是可达的。这个比较好理解。因为你到达i点肯定要经过前面的一个点，这个依次推知可知前面所有的点可达。
所以我们不需要数组来记录结果，只要默认i点前全部可达就行了。
优化点2：如果某点不可达了，直接返回false。不需要再往后计算。
返回值：如果全部扫完仍没有返回false,返回true。
-
// DP2.
-
public
boolean
canJump2
(
int
[]
A
)
{
-
if
(
A
==
null
||
A
.
length
==
0
)
{
-
return
false
;
-
}
-
-
int
len
=
A
.
length
;
-
-
for
(
int
i
=
1
;
i
<
len
;
i
++)
{
-
boolean
can
=
false
;
-
for
(
int
j
=
0
;
j
<
i
;
j
++)
{
-
// j can arrive and can jump to i.
-
if
(
A
[
j
]
>=
i
-
j
)
{
-
// 说明i是可达的，置标记位
-
can
=
true
;
-
break
;
-
}
-
}
-
-
// 优化:如果某一步已经到不了了，后面的也不必再计算了.
-
if
(!
can
)
{
-
return
false
;
-
}
-
}
-
-
return
true
;
-
}
3. 递归
思想是，从前至尾扫描，至第一个距离与本点可达的点j，计算j点是否可达。使用递归计算j点的可达性。
其实这里还是用到了贪心的思维。在考虑本点是否可达的时候，我们是考虑与本点最远的一个点是否可达。实际上这也make sense。
假设j点可以到达i点，那么后面的点可以不管。
（1）因为如果j点不可达，那么j+1也不可达。如果i不可达，后面的点也可不算。
（2）如果j点可达，并且j点可到达i,那么也没有必要再往后计算了。因为结论已经出来了。
（3）如果j点可达，但j不可达i，那么就继续计算。
-
// 3. DFS.
-
public
static
boolean
canJump3
(
int
[]
A
)
{
-
if
(
A
==
null
||
A
.
length
==
0
)
{
-
return
false
;
-
}
-
-
return
canJump
(
A
,
A
.
length
-
1
);
-
}
-
-
public
static
boolean
canJump
(
int
[]
A
,
int
index
)
{
-
if
(
index
==
0
)
{
-
return
true
;
-
}
-
-
for
(
int
i
=
0
;
i
<=
index
-
1
;
i
++)
{
-
if
(
A
[
i
]
>=
index
-
i
)
{
-
return
canJump
(
A
,
i
);
-
}
-
}
-
-
return
false
;
-
}
4. 贪心法
我们现在来使用贪心法One pass解决此问题。
维护一个right (表示右边能跳到的最远的点），从左往右扫描，根据当前可跳的步骤不断更新right ,当right到达终点，即可返回true. 若更新完right后，right未动，并且index = right，而且这时没到达终点，代表我们不可能到达终点了。（当前index的可跳值应该是0）。
-
// solution 3: one pass.
-
public
boolean
canJump
(
int
[]
A
)
{
-
// 4:42
-
if
(
A
==
null
)
{
-
return
false
;
-
}
-
-
int
len
=
A
.
length
;
-
-
int
right
=
0
;
-
for
(
int
i
=
0
;
i
<
A
.
length
;
i
++)
{
-
right
=
Math
.
max
(
right
,
i
+
A
[
i
]);
-
if
(
right
==
len
-
1
)
{
-
return
true
;
-
}
-
-
if
(
i
==
right
)
{
-
return
false
;
-
}
-
}
-
-
return
true
;
-
}
对于大厂面试中高频出现的经典题，我们需要了解它的不同解法，有的大厂不喜欢你一上来就秒掉题目，而更重视你一步步根据题目优化解法，最后得到最优解的解题思路和过程。
另外即使运气真的很不好碰到了新题，做过的高频题也会激发你解题的思路。
算法面试高频题班免费试听，攻略更多大厂常考题型。
转载：https://blog.csdn.net/JiuZhang_ninechapter/article/details/105930329