818. Race Car (Hard)
https://leetcode.com/problems/race-car/
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
.
Solutions
class Solution {
private class Node {
int position, speed, steps;
Node(int position, int speed, int steps) {
this.position = position;
this.speed = speed;
this.steps = steps;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Node)) {
return false;
}
Node node = (Node) o;
return position == node.position && speed == node.speed;
}
@Override
public int hashCode() {
return Objects.hash(position, speed);
}
}
public int racecar(int target) {
if (target == 0) {
return 0;
}
Set<Node> done = new HashSet<>();
Queue<Node> queue = new ArrayDeque<>();
Node start = new Node(0, 1, 0);
done.add(start);
queue.offer(start);
while (!queue.isEmpty()) {
Node curr = queue.poll();
// Turn over to opposite direction, at current time point, remain same position
Node c2 = new Node(curr.position, curr.speed < 0 ? 1 : -1, curr.steps + 1);
if (!done.contains(c2)) {
queue.offer(c2);
done.add(c2);
}
// Position stays the same, no need to check if reach the target
// If current position exceeds 2x target, walking too far away, turn over
if (Math.abs(curr.position) >= Math.abs(target * 2)) {
continue;
}
// Proceed along the axis
Node c1 = new Node(curr.position + curr.speed, curr.speed * 2, curr.steps + 1);
// do not walk the walked steps
if (!done.contains(c1)) {
queue.offer(c1);
done.add(c1);
}
// reach the target
if (target == c1.position) {
return c1.steps;
}
}
return -1;
}
}