Leetcode 836 Solution

This article provides solution to leetcode question 836 (race-car)

https://leetcode.com/problems/race-car

Solution

class Solution: def racecar(self, target: int) -> int: q = collections.deque() visited = set()
q.append((0, 1)) visited.add((0, 1))
ans = 0 while True: s = len(q)
for _ in range(s): pos, speed = q.popleft()
if pos == target: return ans
pos1, speed1 = pos + speed, 2 * speed if (pos1, speed1) not in visited and max(abs(pos1), abs(speed1)) <= 2 * target: q.append((pos1, speed1)) visited.add((pos1, speed1))
if speed > 0: pos2, speed2 = pos, -1 else: pos2, speed2 = pos, 1
if (pos2, speed2) not in visited: q.append((pos2, speed2)) visited.add((pos2, speed2))
ans += 1
return ans