forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathodd-even-jump.py
More file actions
86 lines (70 loc) · 2.14 KB
/
odd-even-jump.py
File metadata and controls
86 lines (70 loc) · 2.14 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
class Solution(object):
def oddEvenJumps(self, A):
l = len(A)
odd_jump = [-1]*l #odd_jump[i], when odd jump from index i, what index it is going to land
even_jump = [-1]*l #even_jump[i], when even jump from index i, what index it is going to land
odd = [False]*l #odd[i], can index i, starting by odd jump, go to the end
even = [False]*l #even[i], can index i, starting by even jump, go to the end
odd[-1] = True
even[-1] = True
#construct odd_jump
stack = []
for n, i in sorted((n, i) for i, n in enumerate(A)):
while stack and stack[-1]<i:
odd_jump[stack.pop()] = i
stack.append(i)
#construct even_jump
stack = []
for n, i in sorted((-n, i) for i, n in enumerate(A)):
while stack and stack[-1]<i:
even_jump[stack.pop()] = i
stack.append(i)
for i in reversed(xrange(l-1)):
if odd_jump[i]!=-1:
odd[i] = even[odd_jump[i]]
if even_jump[i]!=-1:
even[i] = odd[even_jump[i]]
return sum(odd)
# Naive Approach
class Solution(object):
def oddEvenJumps(self, A):
def jump(start, odd):
curr = None
if odd:
temp.add(start)
n = float('inf')
for i in xrange(start+1, len(A)):
val = A[i]
if i not in visited and val>=A[start] and val<n:
n = val
curr = i
else:
n = float('-inf')
for i in xrange(start+1, len(A)):
val = A[i]
if i not in visited and val<=A[start] and val>n:
n = val
curr = i
return curr
opt = set()
not_opt = set()
end = len(A)-1
for i in xrange(len(A)):
if i in opt or i in not_opt: continue
odd = True
curr = i
temp = set()
visited = set()
temp.add(i)
while True:
print curr
visited.add(i)
if curr==None:
not_opt.update(temp)
break
if curr==end:
opt.update(temp)
break
curr = jump(curr, odd)
odd = not odd
return len(opt)