-
Notifications
You must be signed in to change notification settings - Fork 35
/
55_Jump_Game.py
42 lines (34 loc) · 1022 Bytes
/
55_Jump_Game.py
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
class Solution_greedy:
def canJump(self, nums) -> int:
if not nums or len(nums) == 1:
return False
des = len(nums) - 1
i = 0
max_range = 0
nxt = 0
while i < des:
if i + nums[i] >= des:
return True
for r in range(i + 1, i + nums[i] + 1):
if r + nums[r] > max_range:
max_range = r + nums[r]
nxt = r
if i == nxt:
return False
else:
i = nxt
class Solution_backforward:
def canJump(self, nums) -> int:
if not nums or len(nums) == 1:
return True
des = len(nums) - 1
for i in range(des - 1, -1, -1):
if i + nums[i] >= des:
des = i
if des == 0:
return True
return des == 0
# Test
s = Solution_backforward()
print("False: ", s.canJump([1, 2, 0, 0, 0, 6]))
print("True: ", s.canJump([1, 2, 3, 2, 0, 6]))