818. Race Card
Your car starts at position 0 and speed +1 on an infinite number line. (Your car can go into negative positions.)
Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).
When you get an instruction "A", your car does the following: position += speed, speed *= 2
.
When you get an instruction "R", your car does the following: if your speed is positive then speed = -1
, otherwise speed = 1
. (Your position stays the same.)
For example, after commands "AAR", your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1.
Now for some target position, say the length of the shortest sequence of instructions to get there.
Example 1:
Input:
target = 3
Output: 2
Explanation:
The shortest instruction sequence is "AA".
Your position goes from 0->1->3.
Example 2:
Input:
target = 6
Output: 5
Explanation:
The shortest instruction sequence is "AAARA".
Your position goes from 0->1->3->7->7->6.
Note:
1 <= target <= 10000
.
Thoughts:
Dijistra + prunning: TLE
Since A is always moving faster: we can first always A until reaching the target (detecting whether passed the target), and then turn back (Original Post)
Code:
Dijkstra:
class Solution: def racecar(self, target: int) -> int: hq = [(0, 0, 1)] # seq_len, pos, speed, pos_record = set() while True: seq_len, pos, speed = heapq.heappop(hq) if pos == target: return seq_len # Pruning if (pos, speed) in pos_record: continue pos_record.add((pos, speed)) # A heapq.heappush(hq, (seq_len + 1, pos + speed, speed * 2 )) # R rev_speed = -1 if speed > 0 else 1 heapq.heappush(hq, (seq_len + 1, pos, rev_speed))
Last updated
Was this helpful?