跳跃游戏

发表于   |   分类于   |     |  
  |  

跳跃游戏1

问题描述：给出一个非负整数数组，你最初定位在数组的第一个位置。数组中的每个元素代表你在那个位置可以跳跃的最大长度。判断你是否能到达数组的最后一个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    /**
     * @param A: A list of integers
     * @return: The boolean answer
     */
    public boolean canJump(int[] A) {
        for(int i=0;i<A.length;){
            if(A[i]==0&&i!=A.length-1){
                return false;
            }
            if(A[i]>=A.length-i-1){
                return true;
            }
            if(A[i]!=0&&A[i]<A.length-i-1){
                while(A[i]>1&&A[i+A[i]]==0){        //防止不走的情况
                    A[i]--;
                }
                i=i+A[i];
            }
        }
        return true;
    }
}

跳跃游戏2

问题描述：给出一个非负整数数组，你最初定位在数组的第一个位置。数组中的每个元素代表你在那个位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

样例
给出数组A = [2,3,1,1,4]，最少到达数组最后一个位置的跳跃次数是2(从数组下标0跳一步到数组下标1，然后跳3步到数组的最后一个位置，一共跳跃2次)。

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
public class Solution {
    /**
     * @param A: A list of lists of integers
     * @return: An integer
     */
    public int jump(int[] A) {
        int count=0;
        int k=0;
        int temp=0;
        int max=0;
        
        for(int i=0;i<A.length;){
                if(A[i]==0&&i!=A.length-1){
                    return 0;
                }
                if(A[i]>=A.length-i-1){
                    count++;
                    break;
                }
                if(A[i]!=0&&A[i]<A.length-i-1){
                    k=1;
                    while(k<=A[i]){
                        if(A[i+k]+k>max){
                            temp=k;
                            max=A[i+k]+k;
                        }
                        k++;
                    }
                    i=i+temp;
                    count++;
                }
            }
            return count;
        }
}