-
Notifications
You must be signed in to change notification settings - Fork 265
/
044 Jump Game II.py
72 lines (59 loc) · 2.03 KB
/
044 Jump Game II.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
"""
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.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last
index.)
"""
__author__ = 'Danyang'
class Solution:
def jump_TLE(self, A):
"""
bfs
:param A: a list of integers
:return: integer, minimum number of jumps
"""
if not A:
return 0
length = len(A)
counter = 0
dp = [[] for _ in A]
q = []
q.append(0)
while q:
current_level = q
q = []
for ind in current_level:
if ind>=length-1:
return counter
for j in xrange(ind+1, ind+A[ind]+1):
if j not in current_level: # avoid duplicate
q.append(j)
counter += 1
return counter
def jump(self, A):
"""
Simplified bfs, use pointers to scan the array.
Algorithm: Two Pointers
gmax, record the max reachable index (absolute position) from the sliding window
:param A: a list of integers
:return: integer, minimum number of jumps
"""
length = len(A)
counter = 0
start = 0
end = 1 # max reach [0, 1)
gmax = 0
while end<length: # when end==length, it has already reached the last item
if not start<end: return 0 # avoid dead loop
for i in xrange(start, end):
gmax = max(gmax, A[i]+i)
counter += 1
start = end
end = gmax+1
return counter
if __name__=="__main__":
print Solution().jump([3, 2, 1, 0, 4])
assert Solution().jump([2,3,1,1,4])==2