55. Jump Game
Difficulty: Medium
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.
Solution
使用有向图遍历，超时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
36
37
38
39
40
41
42class Solution {
public boolean canJump(int[] nums) {
if(null == nums)return false;
int len = nums.length;
if(len==0)return false;
if(len==1)return true;
List<List<Integer>> graph = new ArrayList<>(len);
// 初始化有向图
for(int i=0;i<len-1;i++){
List<Integer> list = new ArrayList<>();
graph.add(list);
int n = nums[i];
for(int j=1;j<=n&&j<=len-1;j++){
list.add(i+j);
}
}
int[] visited = new int[len];
LinkedList<Integer> q = new LinkedList<>();
q.add(0);
while(!q.isEmpty()){
int pos = q.getFirst();
q.removeFirst();
if(visited[pos]==1)continue;
List<Integer> list = graph.get(pos);
//System.out.println(list);
System.out.println(pos);
for(int n:list){
//System.out.print(" "+n);
if(n==len-1)return true;
q.addLast(n);
}
visited[pos]=1;
}
return false;
}
}
直接拓展右边界1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public boolean canJump(int[] nums) {
if(null == nums)return false;
int len = nums.length;
if(len==0)return false;
if(len==1)return true;
int maxR = 0;
for(int i=0;i<len-1;i++){
if(i<=maxR){
int r = i+nums[i];
if(maxR<r)maxR = r;
if(maxR>=len-1)return true;
}else{
return false;
}
}
return false;
}
}