-
Notifications
You must be signed in to change notification settings - Fork 0
/
054 Jump Game.py
executable file
·105 lines (82 loc) · 2.68 KB
/
054 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
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
"""
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.
"""
__author__ = 'Danyang'
class Solution:
def canJump_TLE(self, A):
"""
dp with data structure.
complicated
Time Limit Exceeded
:param A: a list of integers
:return: a boolean
"""
length = len(A)
dp = [set([index]) for index in range(length)]
for ind, val in enumerate(A):
if ind!=0 and len(dp[ind])<2:
continue
# jump forward
for i in xrange(ind+1, ind+val+1):
if i>=length:
break
for item in dp[ind]:
dp[i].add(item)
return 0 in dp[-1]
def canJump_TLE2(self, A):
"""
Simplified
forward dp to fill True value if can jump
O(N^2)
Time Limit Exceeds
:param A:
:return:
"""
l = len(A)
dp = [False for _ in xrange(l+1)] # last one is dummy
dp[0] = True
for ind, val in enumerate(A):
if dp[ind]:
for i in xrange(1, val+1): # now jumping
if ind+i<l+1:
dp[ind+i] = True
else:
break
return dp[-1]
def canJump(self, A):
"""
dp
dp[i] represents at index i from which the max index (absolute position) it can reach
dp[i] = max(dp[i-1], A[i]+i)
path not recorded, information loss, but sufficient for this question
scanning
O(N)
:param A: a list of integers
:return: a boolean
"""
l = len(A)
# trivial
if l<=1:
return True
# dp = [-1]*(l-1) # normally starting from \phi
dp = [-1 for _ in xrange(l)] # no need dummy here
dp[0] = A[0]+0 # reachable index (absolute index)
for i in xrange(1, l):
# check terminal condition first
# able to reach the end index
if dp[i-1]>=l-1: # directly reach the end
return True
# fail to reach current index
if dp[i-1]<i:
return False
# transition function
dp[i] = max(dp[i-1], A[i]+i) # PoP - Principle of Optimality
return False
if __name__=="__main__":
assert Solution().canJump([2, 3, 1, 1, 4])==True
assert Solution().canJump([3, 2, 1, 0, 4])==False