题目

给定一个非负整数数组,最初位于数组的第一个位置。数组中的元素代表你在该位置可以跳跃的最大长度,你的目的是到达数组的最后一个位置。(假设你总是可以到达数组的最后一个位置,即除了最后一个位置,其他值不能为0)

例如:
输入:[2,3,1,1,4]
输出:2
解释:跳到最后一个位置的最小跳跃数是 2。
从下标0跳到下标为1的位置,跳一步,然后跳3步达到数组的最后一个位置。

思路

即在跳跃距离内,选择一个下一次跳的最远的地方。

实现

作为一个算法渣渣,这种是第一时间能想到的方法,肯定不是最优解。这种最差情况的时间复杂度是n^2,最好情况是n,所以总体时间复杂度是nlogn么。。。不知道怎么算~~~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
<?php
function getShortestValue(array $arr)
{
$count = 0;
$length = count($arr);
for ($i = 0; $i < $length;) {
$count++;

$current_value = $i + $arr[$i];
// 一步到位,跳出循环
if ($current_value >= $length - 1) {
return $count;
}

$max_value = 0;
for ($j = $i + 1; $j <= $current_value; $j++) {
$count++;

$tmp = $j + $arr[$j];
if ($tmp >= $length - 1) {
return $count;
}
if ($tmp >= $max_value) {
$max_value = $tmp;
}
}
$i = $max_value;
}
return $count;
}

$arr = [1, 2, 3, 1, 3, 4, 5, 1, 2];
$arr2 = [2, 3, 1, 1, 4];
echo getShortestValue($arr), "\n"; // 5
echo getShortestValue($arr2), "\n"; // 2

总结:好久不接触算法,已经忘光了,这种算是简单的,却需要花这么久时间,反思。
解完才想起来,应该是要用最短路径方法去解的