-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathJumpGame.java
More file actions
144 lines (136 loc) · 4.01 KB
/
Copy pathJumpGame.java
File metadata and controls
144 lines (136 loc) · 4.01 KB
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
package MyArrays;
import org.junit.Test;
/**
* @description: 描述 Medium
* @author: dekai.kong
* @date: 2018-12-10 14:48
* @from https://leetcode.com/problems/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.
*
* Example 1:
*
* Input: [2,3,1,1,4]
* Output: true
* Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
* Example 2:
*
* Input: [3,2,1,0,4]
* Output: false
* Explanation: You will always arrive at index 3 no matter what. Its maximum
* jump length is 0, which makes it impossible to reach the last index.
*
* 解法:
* 主要看必经之路上有没有0,如果有0 那就到不了,如果没有 那就肯定可以到
*/
public class JumpGame {
public JumpGame() {
}
/**
* 递归法 未完成
* @param nums
* @return
*/
public boolean canJump2(int[] nums) {
return doRecursive(0,nums);
}
public boolean doRecursive(int index,int[] nums){
for (int i = index; i < nums.length; ) {
int curinx = i+nums[i];
if(curinx >= nums.length-1){
return true;
}else if(nums[curinx] == 0){
for (int j = nums[i]-1; j > 0; j--) {
if(nums[curinx-1] > 0){
i += j;
if(doRecursive(i,nums)){
return true;
}else{
i -= j;
}
}
}
return false;
}else{
i = curinx;
}
}
return false;
}
/**
* Runtime: 5 ms, faster than 74.77% of Java online submissions for Jump Game.
* 去掉fill后
* Runtime: 4 ms, faster than 95.26% of Java online submissions for Jump Game.
* @param nums
* @return
*/
public boolean canJump23(int[] nums) {
int[] myidex = new int[nums.length];
// Arrays.fill(myidex,0);
int curinx = 0;
while(curinx<nums.length-1){
curinx = curinx+nums[curinx];
if(curinx == 0){
return false;
}
if(curinx >= nums.length-1){
return true;
}else if(nums[curinx] == 0){
myidex[curinx] = -1;
int backint = 0;
for (int i = curinx; i >= 0 ; i--) {
if(myidex[i] == -1) {
backint += -1;
continue;
}else if (myidex[i] == 1||myidex[i] == 0){
if(backint + nums[i] > 0){
myidex[i] = 1;
curinx = i + nums[i];
break;
}else{
myidex[i] = -1;
backint += -1;
}
}
curinx = i;
}
if(curinx == 0){
return false;
}
}else{
myidex[curinx] = 1;
}
}
return true;
}
/**
* leetcode
* @param arr
* @return
*/
public boolean canJump(int[] arr) {
int maxindex=arr[0];
int n=arr.length;
for (int i = 1; i <n; i++) {
if(i<=maxindex)
{
if(maxindex<i+arr[i])
maxindex=i+arr[i];
}
}
if(maxindex>=n-1)
return true;
else
return false;
}
@Test
public void test() {
System.out.println(canJump(new int[]{2,3,0,1,0,4}));
System.out.println(canJump(new int[]{1,3,3,1,0,4}));
System.out.println(canJump(new int[]{3,0,8,2,0,0,1}));
System.out.println(canJump(new int[]{1,0,2}));
}
}