forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
minimum-sideway-jumps.py
37 lines (34 loc) · 970 Bytes
/
minimum-sideway-jumps.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
# Time: O(n)
# Space: O(1)
# greedy solution
class Solution(object):
def minSideJumps(self, obstacles):
"""
:type obstacles: List[int]
:rtype: int
"""
result, lanes = 0, set([2])
for i in xrange(len(obstacles)-1):
lanes.discard(obstacles[i+1])
if lanes:
continue
result += 1
lanes = set(j for j in xrange(1, 4) if j not in [obstacles[i], obstacles[i+1]])
return result
# Time: O(n)
# Space: O(1)
# dp solution
class Solution2(object):
def minSideJumps(self, obstacles):
"""
:type obstacles: List[int]
:rtype: int
"""
dp = [1, 0, 1]
for i in obstacles:
if i:
dp[i-1] = float("inf")
for j in xrange(3):
if j+1 != i:
dp[j] = min(dp[0]+(j != 0), dp[1]+(j != 1), dp[2]+(j != 2))
return min(dp)