Package g0801_0900.s0818_race_car

Class Solution

java.lang.Object
g0801_0900.s0818_race_car.Solution
public class Solution extends Object
818 - Race Car.<p>Hard</p> <p>Your car starts at position <code>0</code> and speed <code>+1</code> on an infinite number line. Your car can go into negative positions. Your car drives automatically according to a sequence of instructions <code>'A'</code> (accelerate) and <code>'R'</code> (reverse):</p> <ul> <li>When you get an instruction <code>'A'</code>, your car does the following: <ul> <li><code>position += speed</code></li> <li><code>speed *= 2</code></li> </ul> </li> <li>When you get an instruction <code>'R'</code>, your car does the following: <ul> <li>If your speed is positive then <code>speed = -1</code></li> <li>otherwise <code>speed = 1</code>Your position stays the same.</li> </ul> </li> </ul> <p>For example, after commands <code>&quot;AAR&quot;</code>, your car goes to positions <code>0 --> 1 --> 3 --> 3</code>, and your speed goes to <code>1 --> 2 --> 4 --> -1</code>.</p> <p>Given a target position <code>target</code>, return <em>the length of the shortest sequence of instructions to get there</em>.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> target = 3</p> <p><strong>Output:</strong> 2</p> <p><strong>Explanation:</strong></p> <p>The shortest instruction sequence is &ldquo;AA&rdquo;.</p> <p>Your position goes from 0 &ndash;> 1 &ndash;> 3.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> target = 6</p> <p><strong>Output:</strong> 5</p> <p><strong>Explanation:</strong></p> <p>The shortest instruction sequence is &ldquo;AAARA&rdquo;.</p> <p>Your position goes from 0 &ndash;> 1 &ndash;> 3 &ndash;> 7 &ndash;> 7 &ndash;> 6.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= target <= 10<sup>4</sup></code></li> </ul>

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • racecar

      public int racecar(int target)