Algorithm
Problem Name: 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 += speedspeed *= 2
- When you get an instruction
'R', your car does the following:- If your speed is positive then
speed = -1 - otherwise
speed = 1
- If your speed is positive then
For example, after commands "AAR", your car goes to positions 0 --> 1 --> 3 --> 3, and your speed goes to 1 --> 2 --> 4 --> -1.
Given a target position target, return 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.
Constraints:
1 <= target <= 104
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
const racecar = function (target) {
const dp = new Array(target + 1).fill(0)
for (let i = 1; i < = target; i++) {
dp[i] = Number.MAX_VALUE
let m = 1,
j = 1
for (; j < i; j = (1 << ++m) - 1) {
for (let q = 0, p = 0; p < j; p = (1 << ++q) - 1) {
dp[i] = Math.min(dp[i], m + 1 + q + 1 + dp[i - (j - p)])
}
}
dp[i] = Math.min(dp[i], m + (i == j ? 0 : 1 + dp[j - i]))
}
return dp[target]
}
Input
Output
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def racecar(self, target):
q, cnt, used = [(0, 1)], 0, {(0, 1)}
while q:
new = []
for pos, speed in q:
if pos == target:
return cnt
elif pos > 20000 or -20000 > pos:
continue
if (pos + speed, speed * 2) not in used:
new.append((pos + speed, speed * 2))
used.add((pos + speed, speed * 2))
if speed > 0 and (pos, -1) not in used:
new.append((pos, -1))
used.add((pos, -1))
elif speed < 0 and (pos, 1) not in used:
new.append((pos, 1))
used.add((pos, 1))
q = new
cnt += 1
Input
Output
#3 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0818_RaceCar
{
private const int INT_BITS = sizeof(int) * 8; // compile time constant
public int Racecar(int target)
{
var dp = new int[target + 1];
for (int i = 1; i < = target; i++)
dp[i] = int.MaxValue;
dp[0] = 0;
for (int i = 1; i < = target; i++)
{
var k = INT_BITS - GetLeadingZeros(i);
if ((1 << k) - 1 == i)
{
dp[i] = k;
continue;
}
for (int q = 0; q < k - 1; q++)
dp[i] = Math.Min(dp[i], k + q + 1 + dp[i - ((1 << (k - 1)) - (1 << q))]);
if ((1 << k) - 1 - i < i)
dp[i] = Math.Min(dp[i], k + 1 + dp[(1 << k) - 1 - i]);
}
return dp[target];
}
// https://stackoverflow.com/questions/10439242/count-leading-zeroes-in-an-int32
private int GetLeadingZeros(int x)
{
// do the smearing
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
// count the ones
x -= x >> 1 & 0x55555555;
x = (x >> 2 & 0x33333333) + (x & 0x33333333);
x = (x >> 4) + x & 0x0f0f0f0f;
x += x >> 8;
x += x >> 16;
return INT_BITS - (x & 0x0000003f); // subtract # of 1s from 32
}
}
}
Input
Output