# 818     Race Car

## 818. [Race Car](https://leetcode.com/problems/race-car/description/)

## 1. Question

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`.

## 2. Implementation

**(1) BFS**

题目要求我们找出**最短**的instruction,使得car可以从0这个位置到target位置。已知instruction只有两种，A表示加速，R表示调头。由于题目给了我们初始状态，并要求我们利用最短的方式到达最终状态，很容易让我们想到用BFS。 BFS的思路比较直接，就是用queue存每个状态的两个变量: 当前位置和当前速度，然后对于每个状态都分别进行加速和掉头的操作，如果符合条件则放到queue中继续搜索。这里为了提高算法的效率，我们发现过程中可能会有重复的状态出现，所以我们需要用一个visited的set去重，另一可以优化的地方是，如果当前的位置nexPos离target的距离比初始位置离target的距离还要远，则没必要对这个位置继续进行搜索

```java
class Solution {
    public int racecar(int target) {
        Queue<int[]> queue = new LinkedList();
        queue.add(new int[] {0, 1});

        Set<String> visited = new HashSet();
        visited.add("0/1");

        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                int[] curInfo = queue.remove();
                int curPos = curInfo[0];
                int curSpeed = curInfo[1];

                if (curPos == target) {
                    return level;
                }

                // Accelerate
                int nextPos = curPos + curSpeed;
                int nextSpeed = 2 * curSpeed;
                int[] nextInfo = new int[] {nextPos, nextSpeed};
                String key = nextPos + "/" + nextSpeed;

                // if the distance from target for nextPos is greater than the initial position (0), 
                // we don't consider nextPos
                if (!visited.contains(key) && Math.abs(nextPos - target) < target) {
                    visited.add(key);
                    queue.add(nextInfo);
                }

                // Reverse
                nextPos = curPos;
                nextSpeed = curSpeed > 0 ? -1 : 1;
                nextInfo = new int[] {nextPos, nextSpeed};
                key = nextPos + "/" + nextSpeed;

                // if the distance from target for nextPos is greater than the initial position (0), 
                // we don't consider nextPos
                if (!visited.contains(key) && Math.abs(nextPos - target) < target) {
                    visited.add(key);
                    queue.add(nextInfo);
                }
            }
            ++level;
        }
        return -1;
     }
}
```

## 3. Time & Space Complexity

时间复杂度O(2 ^ n), n为instruction的长度，因为在BFS过程中，我们对accelerate和reverse两种操作都进行了尝试, 所以总的时间复杂度是2^n, 空间复杂度O(2 ^ n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/heap/818-race-car.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.