Jump Game

leetcode OJ:https://oj.leetcode.com/

昨天晚上到今天早上A的Jump Game Medium。开始有很多情况没有考虑，后面根据错误慢慢改

思路注释中有说明

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 //如果没有0是肯定可以到达last位置的
 2 //记录0的个数count_zero
 3 //记录0的位置array_index_zero[]
 4 //从0最左边位置i开始向开始位置查找  并记录到0的距离step
 5 //如果有A[i] > step说明可以到达0右边的第一个数字
 6 //跳出循环，验证下一个0
 7 //如果每个0都可以跳到0右边的第一个数
 8 //说明是可以到达last位置的
 9 
10 //注意考虑A中只有1个元素
11 //A中如果有连续出现的0
12 
13 public class Solution {
14     public boolean canJump(int[] A) {
15         int count_zero = 0;//记录数组中0的个数
16         int array_index_zero[];//这里不知道0的个数，所以没有new
17         
18         //1个元素直接返回true
19         if(1 == A.length)
20             return true;
21         
22         //记录0的个数
23         for(int i = 0; i < A.length; i++){
24             if(0 == A[i]){
25                 count_zero ++;
26             }
27         }
28         if(0 == count_zero)
29             return true;//全是正数,可以到达last位置,返回true
30         //记录0的在数组A中的位置
31         array_index_zero = new int[count_zero];//不知道zero拼对没有
32         int temp = 0;
33         for(int i = 0; i < A.length; i++){
34             if(0 == A[i]){
35                 array_index_zero[temp] = i;
36                 temp ++;
37             }
38         }
39         boolean isCan = false;//默认不能到达last位置
40         //验证所有的0是否都能到达0右边第一个数字
41         for(int i = 0; i <= count_zero - 1; i++){
42             //开始验证每个0
43 
44             while(!validZero(A, array_index_zero[i])){//有个元素不行，说明就不能到达last位置
45                 //isCan = false;
46                 return false;
47             }            
48         }
49         return true;
50     }
51     //验证index位置的0是否可以到达0右边第一个元素
52     //3,0,0,0这个确实有点烦来着
53     public boolean validZero(int A[], int index){
54         boolean isValid = false;//默认不能到达
55         int steps = 1;//距离index的距离
56         //如果0是最后一个元素，返回true
57         if(A.length - 1 == index)
58             return true;
59         //找出左边连续出现的0
60         while(index > 0 && 0 == A[--index])
61             steps++;
62         
63         //index++;
64         for(int i = index; i >= 0 && 0 != A[i]; i--){
65             if(A[i] > steps){
66                 isValid = true;
67                 break;//只要有一个大于这个距离就可以跳出
68             }
69             steps++;
70         }
71         
72         return isValid;
73     }
74 }

PS:别人的贪心算法

 1 public class Solution {
 2     public boolean canJump(int[] A) {
 3         if(0 == A.length || 1 == A.length)
 4             return true;
 5         int maxcan = 0;
 6         
 7         for(int i = 0; i < A.length; i++){
 8             if(maxcan >= A.length - 1)
 9                 return true;
10             maxcan = Math.max(maxcan, A[i] + i);
11             if(maxcan == i){
12                 return false;
13             }
14         }
15         return true;
16     }
17 }

找出每一次的最大距离，如果可以到last位置,返回true。

只有当第i次时maxcan == i即第i的位置为0而前面所有位置不可能跳过这个0返回false

这里贪心算法还不是很了解，还需要多熟悉一下