818. 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
.
Rust Solution
struct Solution;
use std::collections::HashMap;
use std::collections::VecDeque;
impl Solution {
fn racecar(target: i32) -> i32 {
let mut queue: VecDeque<(usize, i32, i32)> = VecDeque::new();
let mut states: HashMap<(i32, i32), usize> = HashMap::new();
queue.push_back((0, 0, 1));
states.insert((0, 1), 0);
while let Some((length, position, speed)) = queue.pop_front() {
if position == target {
return length as i32;
}
for (p, s) in Self::next(position, speed) {
if p > target + target / 3 || p < -target / 3 {
continue;
}
if states.contains_key(&(p, s)) && states[&(p, s)] <= length + 1 {
continue;
}
*states.entry((p, s)).or_default() = length + 1;
queue.push_back((length + 1, p, s));
}
}
0
}
fn next(position: i32, speed: i32) -> Vec<(i32, i32)> {
vec![
(position + speed, speed * 2),
(position, if speed > 0 { -1 } else { 1 }),
]
}
}
#[test]
fn test() {
let target = 3;
let res = 2;
assert_eq!(Solution::racecar(target), res);
let target = 6;
let res = 5;
assert_eq!(Solution::racecar(target), res);
}
Having problems with this solution? Click here to submit an issue on github.