跳跃游戏

在跳跃游戏中,要明白贪心法则的定义。贪心法则:最基本的理解就是,每次选择当前最优的解,到最后就能得到整个问题的最优解法。

1.题目

给定数组arr,arr[i]=k代表可以从位置i向右跳1~k个距离。比如,arr[2] == 3,代表从位置2可以调到位置3、位置4或位置5。如果从位置0出发,返回最少跳几次能跳到arr最后的位置上。

2.举例

1
arr = {3,2,3,1,1,4}

arr[0]==3,选择跳到位置2:arr[2]==3,可以跳到最后的位置。所以返回2.

3.解题思路(利用贪心法则)

具体过程如下:

  • 1.整形变量jump,代表目前跳了多少步。(就是跳了几次,就是题目要求的值)。整形变量cur,代表如果只能跳jump步,最远能够到达的位置。(换句话说,按照上面的例子:假如你jump一次,从0位置开始a[0]==3,则你可以到达的最远的位置就是1,2,3)。整型变量next,代表如果在多跳一步,最远能够到达的位置。初始时,jump=0,cur=0,next=0.

image.png

2.从左到右遍历arr,假设遍历到位置i。

  • 2.1如果cur>=i,说明jump步可以达到位置i,此时什么也不做。
  • 2.2如果cur<i,说明只跳jump不能到达位置i,需要多跳一步才行。此时令jump++cur=next。表示多跳了一步,cur更新成jump+1步能够到达的位置,即next。
  • 2.3将next更新成next = Math.max(next,i+arr[i]);表示下一次多跳一步到达的最远位置。

3.当遍历到arr的尾部时,最终返回jump即可。

image.png

4.具体代码如下

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
/**
* @author zhoujian123@hotmail.com 2018/8/15 15:53
*/
public class JumpGame {

public static int jump(int [] arr){
if (arr == null || arr.length == 0) {
return 0;
}
//代表跳了几次
int jump = 0;
int cur = 0;
int next = 0;
for (int i = 0; i < arr.length; i++) {
if (cur < i){
jump++;
cur = next;
}
next = Math.max(next,i+arr[i]);
}
return jump;
}

public static void main(String[] args) {
int[] arr={3,2,3,1,1,4};
int i = jump(arr);
System.out.println(i);
}
}

贪心方法的时间复杂度为O(n),空间复杂度为O(1)。

文章目录
  1. 1. 1.题目
  2. 2. 2.举例
  3. 3. 3.解题思路(利用贪心法则)
  4. 4. 4.具体代码如下